mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2020-08-08, 16:33   #1
Ensigm
 
Aug 2020

2·3·17 Posts
Question 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?
Ensigm is offline   Reply With Quote
Old 2020-08-08, 18:37   #2
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

2×4,441 Posts
Default

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.
Uncwilly is offline   Reply With Quote
Old 2020-08-08, 19:52   #3
Ensigm
 
Aug 2020

6616 Posts
Default

Quote:
Originally Posted by Uncwilly View Post
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.
Ensigm is offline   Reply With Quote
Old 2020-08-08, 20:09   #4
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

212628 Posts
Default

Maybe James H can look at the server code that does the ECM assignments. It might be time to tweak it.
Uncwilly is offline   Reply With Quote
Old 2020-08-08, 20:14   #5
lycorn
 
lycorn's Avatar
 
Sep 2002
Oeiras, Portugal

24·89 Posts
Default

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.
lycorn is offline   Reply With Quote
Old 2020-08-08, 20:26   #6
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

2×4,441 Posts
Default

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
Uncwilly is offline   Reply With Quote
Old 2020-08-08, 21:18   #7
Ensigm
 
Aug 2020

6616 Posts
Default

Quote:
Originally Posted by lycorn View Post
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.
Ensigm is offline   Reply With Quote
Old 2020-08-08, 22:19   #8
lycorn
 
lycorn's Avatar
 
Sep 2002
Oeiras, Portugal

24·89 Posts
Default

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.
lycorn is offline   Reply With Quote
Old 2020-08-08, 22:50   #9
Ensigm
 
Aug 2020

2×3×17 Posts
Default 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
Ensigm is offline   Reply With Quote
Old 2020-08-09, 03:51   #10
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

2·2,239 Posts
Default

Quote:
Originally Posted by Ensigm View Post
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.
VBCurtis is online now   Reply With Quote
Old 2020-08-09, 04:04   #11
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

2·3·1,193 Posts
Default

Quote:
Originally Posted by Ensigm View Post
Take M35731 as an example:.
This small exponent should be done by a prime95/GMP-ECM combination
Prime95 is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Trial factoring limits TriV Factoring 7 2018-05-30 16:22
Trial Factor Assignment Time Limits Judge Hale Information & Answers 12 2015-07-11 23:48
Factoring/P-1 Benefit question JuanTutors Software 4 2010-11-17 08:34
Result Queries - Factoring Limits S485122 PrimeNet 0 2009-03-10 07:01
trial factoring and P-1 jocelynl Math 8 2006-02-01 14:12

All times are UTC. The time now is 23:26.

Thu Nov 26 23:26:34 UTC 2020 up 77 days, 20:37, 4 users, load averages: 1.14, 1.26, 1.25

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.