mersenneforum.org  

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

Reply
 
Thread Tools
Old 2013-02-22, 19:40   #1
TObject
 
TObject's Avatar
 
Feb 2012

1100101012 Posts
Question ECM for exponents above 20,000,000

Judging by the Exponent Status Distribution report, PrimeNet participants are not expected to return ECM results for exponents above 20,000,000. What is the reason for that? Is diminishing efficiency?

Thanks
TObject is offline   Reply With Quote
Old 2013-02-22, 19:46   #2
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3·29·83 Posts
Default

The time it takes to do one curve is proportional to the exponent in the same way that iteration time is proportional to the exponent.

So above 20M, it just takes way too long to do one curve. (Heck, I'm surprised anybody tries for something more than, say, 5M.)
Dubslow is offline   Reply With Quote
Old 2013-02-22, 20:02   #3
TObject
 
TObject's Avatar
 
Feb 2012

40510 Posts
Default

If someone is really persistent at finding a factor of a given exponent, and TF has been done to a fairly high level, so has the P-1 with good bounds. Would the next logical step be to run ECM?

What is a good strategy then for choosing ECM bounds in regards to the levels of TF and P-1 bounds already done? In particular, do ECM bounds correspond P-1 bounds so if P-1 has not found a factor within these bounds nether will ECM? Or ECM bounds are something else?

Thank you
TObject is offline   Reply With Quote
Old 2013-02-22, 21:17   #4
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

31·101 Posts
Default

If an exponent have been trialfactored to 2^70 that is 70*log10(2) ~ 20 digits, so you should at least start at 25 digit level or higher. From GMP-ECM readme file here is the standard optimal bounds and curve count for the different digit levels:

Code:
       digits D  optimal B1   default B2   expected curves
          20       11e3         1.9e6             74
          25        5e4         1.3e7            214
          30       25e4         1.3e8            430
          35        1e6         1.0e9            904
          40        3e6         5.7e9           2350
But it will take a very long time just for the 214 curves for the 25 digit level.
ATH is online now   Reply With Quote
Old 2013-02-22, 22:10   #5
TObject
 
TObject's Avatar
 
Feb 2012

34×5 Posts
Default

Thank you, that is very helpful.

What about P1 bounds? Are P1 and ECM bounds numerically compatible?

I imagine, for a chance to find a factor, ECM bounds should be above of P-1 already performed…
TObject is offline   Reply With Quote
Old 2013-02-22, 22:28   #6
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

31×101 Posts
Default

GMP-ECM readme again:

Quote:
2 - run once P-1 with 10*B1, and the default B2 chosen by GMP-ECM
So for 25digit instead of B1=50,000 from ecm you use B1=500,000 for P-1.


P-1 is something you run once unless you increase the bounds later. P-1 will find the factor P with 100% certainty IF the factors of P-1 is within the bounds B1 (and 1 factor in the B1-B2 range). With ecm you run many curves with random "seeds" with a small probability of finding the factors.

Last fiddled with by ATH on 2013-02-22 at 22:32
ATH is online now   Reply With Quote
Old 2013-02-22, 22:34   #7
TObject
 
TObject's Avatar
 
Feb 2012

34×5 Posts
Default

Thank you. So, I gather that, unless limited by other factors, ECM bounds can be as low as 1/10th of already run P-1 bounds and ECM still has a chance of finding a factor. Right?

Last fiddled with by TObject on 2013-02-22 at 22:57
TObject is offline   Reply With Quote
Old 2013-02-22, 22:54   #8
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

31×101 Posts
Default

These are the standard "optimal" bounds, yes it works in Prime95 as well.
ATH is online now   Reply With Quote
Old 2013-02-23, 09:58   #9
axn
 
axn's Avatar
 
Jun 2003

2×3×827 Posts
Default

Quote:
Originally Posted by TObject View Post
ECM bounds can be as low as 1/10th of already run P-1 bounds and ECM still has a chance of finding a factor. Right?
ECM bounds are in no way relatable to P-1 bounds. ECM search space is different from P-1 search space. The 1/10th stuff is what you'd call a "rule of thumb". Don't bother.

ATH's first post is the relevant one. But note that for large mersennes, GMP-ECM is not usable -- you have to use P95. And P95 has a different stage 2 bound (default is 100x stage 1) compared to GMP-ECM and therefore recommended # of curves at each level is higher.
axn is online now   Reply With Quote
Old 2013-02-23, 14:06   #10
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by axn View Post
ECM bounds are in no way relatable to P-1 bounds. ECM search space is different from P-1 search space. The 1/10th stuff is what you'd call a "rule of thumb". Don't bother.
My suggestion: Do not bother listening to axn. He does not know what he
is talking about. ECM bounds are related to P-1 bounds.

Read:

Robert Silverman & Samuel Wagstaff Jr.
A Practical Analysis of ECM.
Mathematics of Computation

This paper describes the relationship between P-1 and ECM.

To axn: do us all a favor: Study this subject before making further
erroneous pronouncements.
R.D. Silverman is offline   Reply With Quote
Old 2013-02-23, 15:30   #11
c10ck3r
 
c10ck3r's Avatar
 
Aug 2010
Kansas

54710 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
Robert Silverman & Samuel Wagstaff Jr.
A Practical Analysis of ECM.
Mathematics of Computation
Linky linky?
c10ck3r is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Exponents which don't need any more ECM MatWur-S530113 PrimeNet 8 2016-10-12 08:00
77.9M exponents GP2 Data 9 2016-08-21 14:10
exponents 42M-43M davieddy PrimeNet 11 2008-02-27 10:52
Unreserving exponents(these exponents haven't been done) jasong Marin's Mersenne-aries 7 2006-12-22 21:59
>10,000,000 exponents ninjabill PrimeNet 5 2006-02-07 17:28

All times are UTC. The time now is 07:32.

Wed May 12 07:32:17 UTC 2021 up 34 days, 2:13, 0 users, load averages: 1.20, 1.79, 1.88

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.