Exponents < 2 Million

[wackyeh]

Since one of the other posts mention this range... I'll start a topic...

There has been considerable amount of ECM done in this range... particularly for exponents &lt; 1 Million... Since many exponents have been ECM'd up to 25 digits... it would be useless to attempt to trial-factor them any higher than they already are...

Why?? Although there is a minimal chance that ECM missed a factor... ECM'ing to 25 digits is the equivalent of trial-factoring to 2^83...

Any exponent with ECM done to 25 digits is... therefore... essentially trial-factored higher than the 2^76 limit of Prime95...

Exponents NOT ECM'd completely... or at all... to 25 digits... is of course the exception...

Eric

[cheesehead]

For information on how much ECM factoring has already been performed for various 2^N-1 and 2^N+1 which are not yet completely factored, see:

http://www.mersenne.org/ecmm.htm for 2^N-1, N &lt; 1200

http://www.mersenne.org/ecmp.htm for 2^N+1, N &lt; 1200

http://www.mersenne.org/ecm1.htm for 2^P-1, P prime and 1200 &lt; P &lt; 10000

http://www.mersenne.org/ecm2.htm for 2^P-1, P prime and P > 10000

http://www.mersenne.org/ecmf.htm for Fermat numbers (2^N+1, N is a power of 2)

[geoff]

I thought that once the recommended amount of ECM has been done on an exponent for 25 digit factors, then there is still 1/e chance that a factor smaller than 25 digits remains. So trial factoring one of these exponents from 2^57 to 2^58 should have a 1/57e chance of finding a factor.

Geoff.

[cheesehead]

Originally Posted by geoff

I thought that once the recommended amount of ECM has been done on an exponent for 25 digit factors, then there is still 1/e chance that a factor smaller than 25 digits remains.

AFAIK you are correct.

Just as GIMPS discussions about factoring sometimes include statements like "You're wasting your time TFing past the Prime95 default power-of-2 limit" or "There's no value in doing P-1 to B1/B2 higher than those chosen by Prime95", which neglect to note that the Prime95 default limits are just points at which the efficiency of factor-finding by TF or P-1 balance the efficiency of composite-proving by L-L test, so too do ECM discussions sometimes make statements about the number of curves to be run with certain limits which are more absolute than is justified.

What I have read is that the recommended numbers of ECM curves to run with certain limits are calculated to make the probability of finding a certain-size-or-smaller factor = 1 - (1/e) = 63%. [Edit: See wblipp's more correct note, below, about "If you make "N" tests, each with probability of (1/N) of success, the probability of no successes is 1/e for large N"] They are NOT intended to signal that there is no point in running trial factoring for factors in that range.

Originally Posted by geoff

So trial factoring one of these exponents from 2^57 to 2^58 should have a 1/57e chance of finding a factor.

If I understand correctly, the 1/57e probability would be correct only if the ECM work had been done with limits and number of curves that would leave a 1/e probability of an undiscovered factor under 2^58 (= about 17.5 decimal digits).

If ECM had been done farther than that, such as to the limits recommended for factors of 25 digits or less, then TF from 2^57 to 2^58 would have a lower probability than 1/57e of finding an undiscovered factor.

- - - - - - - - - -

Originally Posted by wackyeh

Since many exponents have been ECM'd up to 25 digits... it would be useless to attempt to trial-factor them any higher than they already are...

If ECM'd only up to 25 digits using the stndard recommended limits and number of curves, then there's still a 1/e (37%) chance of an undiscovered factor of 25 digits (83 bits) or less.

Originally Posted by wackyeh

ECM'ing to 25 digits is the equivalent of trial-factoring to 2^83

... except that TFing to 2^83 without finding a factor would guarantee that there was zero probability of an undiscovered factor of 83 bits or less, while ECMing to 2^83 using the standard recommended limits and number of curves would leave a probability of 37% that there was an undiscovered factor of 83 bits or less.

Originally Posted by wackyeh

Any exponent with ECM done to 25 digits is... therefore... essentially trial-factored higher than the 2^76 limit of Prime95...

Not exactly.

An exponent ECM'd to 25 digits is essentially 63% trial-factored to 2^83, with 37% of the potential factors below 2^83 not yet having been tried.

Edit: note smh's comments below.

- - -

[Edited most of my paragraphs above to reduce the absolutization index of my own statements :) ]

[smh]

An exponent ECM'd to 25 digits is essentially 63% trial-factored to 2^83, with 37% of the potential factors below 2^83 not yet having been tried

Correct, but most of the not tried factors are above 2^76

The chances of missing a 2^76 factor are lower then 37%

But indeed there is still a small chance that a &lt; 20 digit factor goes unnoticed.

It's probably more efficient to run ECM with higher bounds on these numbers (with a good chance of finding larger factors) then continuing trail factoring to 2^60 or so

[wblipp]

Originally Posted by smh

Correct, but most of the not tried factors are above 2^76

The latest version of GMP-ECM has the following table for the tests needed at each level:

[code:1]
digits D optimal B1 B2 expected curves N(B1,B2,D)
15 2e3 1.2e5 30
20 11e3 1.4e6 90
25 5e4 1.2e7 240
30 25e4 1.1e8 500
35 1e6 8.4e8 1100
40 3e6 4.0e9 2900
45 11e6 2.6e10 5500
50 43e6 1.8e11 9000
55 11e7 6.8e11 22000
60 26e7 2.3e12 52000
65 85e7 1.3e13 83000
70 29e8 7.2e13 120000[/code:1]

I think this means that when testing with B1=25e4, if there is a 30 digit factor, there is a probability of 1/500 of finding on any particular test. Likewise, when testing at B1=1e6, if there is a 35 digit factor, there is a probability of 1/1100 of finding it on any particular test. Also, if you shifted from 24e4 to 1e6 after 500 curves at the lower level, and there is a 30 digit factor, the probability that you didn't find it during the 24e4 tests is 1/e. If there is a missed 30 digit factor, you will to continue to possibly find it during the 1e6 tests.

What is the probability of finding that missed 30 digit factor in each 1e6 test? Does it remain at the 1/500 value it had during the 25e4 tests? Does it become the same as the 1/100 value for a 35 digit factor during these tests? Does it become even higher than 1/500 because more nearby numbers are smooth at this level?

I suspect the last (higher than 1/500) is correct - if so, how do you calculate the new probability?

[smh]

I think this means that when testing with B1=25e4, if there is a 30 digit factor, there is a probability of 1/500 of finding on any particular test.

about 1/750 for a 30 digit factor (1/500 for 1/e chance). The chance of finding a 25 digit factor is much higher (although i've no idea how to calculate this.) It is also verry well possible to find factors larger then 30 digits, although the chances are getting lower. The Bounds given in the table are just optimal bounds for finding a certain size factor in the least ammount of time.

I suspect the last (higher than 1/500) is correct - if so, how do you calculate the new probability?

Yes, the probability is higher, but each curve takes longer.

The latest GMP ECM client also has an option to increase the bound automatically after each curve. i think thats a more efficient way to find factors (of unknown size), but it makes it harder to keep track on the progress that has been made on a number

[wblipp]

Originally Posted by smh

about 1/750 for a 30 digit factor (1/500 for 1/e chance).

I think the 1/500 is correct. If you make "N" tests, each with probability of (1/N) of success, the probability of no successes is 1/e for large N - this comes from the Poisson Approximation, or alternatively from the limit (1-1/n)^n = 1/e.