ECM for exponents above 20,000,000

[TObject]

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

[Dubslow]

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.)

[TObject]

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

[ATH]

If an exponent have been trialfactored to 2^70 that is 70*log₁₀(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:

       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.

[TObject]

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…

[ATH]

GMP-ECM readme again:

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.

[TObject]

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?

[ATH]

These are the standard "optimal" bounds, yes it works in Prime95 as well.

[axn]

Originally Posted by TObject

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.

[R.D. Silverman]

Originally Posted by axn

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.

[c10ck3r]

Originally Posted by R.D. Silverman

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

Linky linky?