how much ECM without finding an existing factor

[dbaugh]

Using TF, I found a smallish factor of 1328447 (6765509895590355887). The following curves had already been run without finding this 63-bit factor. What is the worst case known of ECM missing a factor? How many hundred curves does theory say are needed to clear through 63 bits?

1 curves, B1=50000, B2=5000000 by "George Woltman" on 2007-12-18
3 curves, B1=50000, B2=5000000 by "Sturle Sunde" on 2008-10-13
3 curves, B1=50000, B2=5000000 by "Sturle Sunde" on 2009-02-21
3 curves, B1=50000, B2=5000000 by "Tapio Rajala" on 2009-07-26
3 curves, B1=50000, B2=5000000 by "SubPrime" on 2009-11-08
3 curves, B1=50000, B2=5000000 by "James Hintz" on 2010-06-11
3 curves, B1=50000, B2=5000000 by "Bruce" on 2011-02-23
1 curve, B1=50000, B2=5000000 by "Oscar Östlin" on 2011-11-19
3 curves, B1=50000, B2=5000000 by "James Hintz" on 2012-04-10
3 curves, B1=50000, B2=5000000 by "OS1" on 2012-10-30

[c10ck3r]

FWIW, P-1 would take FOREVER to find this, since its a prime k.
I lack sufficient understanding to answer the ECM question, however.

[Dubslow]

According to the well known GMP-ECM estimates, this is the ECM work data in that range:

t        B1   standard curves   Brent-Suyama curves
20     11e3           74                74
25      5e4          221               214
30     25e4          453               430
35      1e6          984               904

This indicates that t20 is 74 curves at B1=11000, while a t25 is 214 curves at 50000, the bounds reported there. A "t20" or "t30" or "t<number>" means that there's a exp(-1) ~ 37% chance of having missed a <number> sized factor. Doing twice the number of curves (or in general x times the number of curves) means that you have a exp(-2) ~ 14% (or exp(-x)) chance of having missed a factor of that size.

That data shows 25 curves done at the t25 level, which is well short of the 214 suggested (and still rather short of 74 curves at the lower t20). It's therefore well within the bounds of chance and reason that a 19 digit factor hadn't been found. One might guess that another 200 curves would *probably* find the factor (and maybe another factor closer to 25 digits than 20).

[Axon]

If a big number has a factor between 2⁶² and 2⁶³, then a probability of findind this factor with 26 ECM curves (B1=50000 and B2=100*B1) is about 0.75 (it may be inaccurate but I hope not very inaccurate).
Therefore it isn't so improbable that the factor was missed. To increase the probability of findind 63-bit factor up to 0.99 you should run about 90 ECM curves.

[henryzz]

Originally Posted by Axon

If a big number has a factor between 2⁶² and 2⁶³, then a probability of findind this factor with 26 ECM curves (B1=50000 and B2=100*B1) is about 0.75 (it may be inaccurate but I hope not very inaccurate).
Therefore it isn't so improbable that the factor was missed. To increase the probability of findind 63-bit factor up to 0.99 you should run about 90 ECM curves.

These probabilities are based on an exponential distribution.
The probability of finding a 20 digit factor with 74 curves at 11e3 is 1-e^-1
With 37 curves 1-e^(-1/2). With n curves 1-e^(-n/74) etc.
99% chance of a 20 digit factor is 341 curves.