mersenneforum.org > Math Does ECM benefit from the trial factoring limits?
 Register FAQ Search Today's Posts Mark Forums Read

 2020-08-08, 16:33 #1 Ensigm   Aug 2020 2×3×19 Posts Does ECM benefit from the trial factoring limits? I know nearly null about the math, but I've read that like P-1 method, the ECM method needs higher bounds in to find larger factors but takes longer time to run. Does knowing the trial factoring limits provide benefit to the ECM bounds and/or the number of curves to try, like the case in P-1 method?
 2020-08-08, 18:37 #2 Uncwilly 6809 > 6502     """"""""""""""""""" Aug 2003 101×103 Posts 948110 Posts If you know that no factor has been found and that there has been TF work done up to a certain size, yes. ECM can then be done looking for factors larger than the largest factor searched for via TF.
2020-08-08, 19:52   #3
Ensigm

Aug 2020

2×3×19 Posts

Quote:
 Originally Posted by Uncwilly If you know that no factor has been found and that there has been TF work done up to a certain size, yes. ECM can then be done looking for factors larger than the largest factor searched for via TF.
Yeah, my thought is that we can use this to optimize assignment rules. Take M35731 as an example: the server is still actively giving out assignments with 3e6 as B1 (I just did one, haha), despite TF has shown it has no factor under 2^65; while if http://www.wraithx.net/math/ecmprobs/ecmprobs.html is correct, even if 4700 curves are performed under that B1 value, the chance of finding a factor larger than 2^65 is 9.75e-6 (You can drag to select a range on that graph).

At this point I'm starting to think it as simply a waste of GHz-hours. If we can start giving assignments with B1=8e8 instead (this is the largest B1 listed at https://www.mersenne.org/report_ecm/, although in this case we should obviously use even higher bounds), and assume the time needed for a curve is proportional to B1, then the same CPU power can be used to test 17 curves, giving a success rate of roughly 2e-4. Still very small, but that is already a 20x improvement.

 2020-08-08, 20:09 #4 Uncwilly 6809 > 6502     """"""""""""""""""" Aug 2003 101×103 Posts 19×499 Posts Maybe James H can look at the server code that does the ECM assignments. It might be time to tweak it.
 2020-08-08, 20:14 #5 lycorn     Sep 2002 Oeiras, Portugal 1,451 Posts I think you are confusing digits and bits. The TF was performed to 65 bits, and the probability you quoted is for finding a 65 digits factor using B1 = 3e6.
 2020-08-08, 20:26 #6 Uncwilly 6809 > 6502     """"""""""""""""""" Aug 2003 101×103 Posts 19×499 Posts 2^65 for that number is in the range of 2,324,976,294,838,206,465 (19 digits) A B1 of 2000 and 500 curves is around 19 digits Last fiddled with by Uncwilly on 2020-08-08 at 20:32
2020-08-08, 21:18   #7
Ensigm

Aug 2020

2×3×19 Posts

Quote:
 Originally Posted by lycorn I think you are confusing digits and bits. The TF was performed to 65 bits, and the probability you quoted is for finding a 65 digits factor using B1 = 3e6.

Oh you're right. I also misinterpreted the graph at http://www.wraithx.net/math/ecmprobs/ecmprobs.html. The "Success Chance" should mean the probability of finding (i.e. not missing) a factor in an interval if there is a factor there, not the overall probability of finding a factor.

 2020-08-08, 22:19 #8 lycorn     Sep 2002 Oeiras, Portugal 1,451 Posts If you run 4700 ECM curves with B1=3e6, the chance of missing a 40-digit factor is ~ 1/e (if there is one...) . Same holds for the various Size/B1 value / number of curves combinations in the table.
 2020-08-08, 22:50 #9 Ensigm   Aug 2020 11410 Posts Conclusion: Not of much use So the conclusion is that TF limits are too small to help anything in tweaking ECM parameters. Even if we have limits to 2^80 (25 digits), it is not obvious how much this will change the optimal crossing point of 5e4 and 2.5e5. Last fiddled with by Ensigm on 2020-08-08 at 23:16
2020-08-09, 03:51   #10
VBCurtis

"Curtis"
Feb 2005
Riverside, CA

127C16 Posts

Quote:
 Originally Posted by Ensigm So the conclusion is that TF limits are too small to help anything in tweaking ECM parameters. Even if we have limits to 2^80 (25 digits), it is not obvious how much this will change the optimal crossing point of 5e4 and 2.5e5.
False- if you know TF was done to 82 bits, you know to not bother with ECM at the 20-digit level, nor at the 25-digit level. Skip right to T30 (B1=25e4).

Similar conclusions can be made about TF to, say, 79 bits- that rules out factors under 24 digits, so I would run less of a T25 and jump to T30-sized curves sooner. In B1 terms, less than a full set of curves at 5e4 and jump to B1=25e4 sooner.

However, it's rather unlikely to have a candidate number that one would TF to 78+ bits *and* consider ECM on. For the size of number for which we ECM, trial-factoring limits are usually 74 bits or lower and starting at B1=5e4 makes sense. So, in practice for GIMPS-factoring, TF doesn't influence our ECM choices.

2020-08-09, 04:04   #11
Prime95
P90 years forever!

Aug 2002
Yeehaw, FL

163538 Posts

Quote:
 Originally Posted by Ensigm Take M35731 as an example:.
This small exponent should be done by a prime95/GMP-ECM combination

 Similar Threads Thread Thread Starter Forum Replies Last Post TriV Factoring 7 2018-05-30 16:22 Judge Hale Information & Answers 12 2015-07-11 23:48 JuanTutors Software 4 2010-11-17 08:34 S485122 PrimeNet 0 2009-03-10 07:01 jocelynl Math 8 2006-02-01 14:12

All times are UTC. The time now is 12:28.

Tue Apr 13 12:28:28 UTC 2021 up 5 days, 7:09, 1 user, load averages: 3.02, 2.80, 2.70