20130110, 23:34  #1 
Aug 2005
118_{10} Posts 
how much ECM without finding an existing factor
Using TF, I found a smallish factor of 1328447 (6765509895590355887). The following curves had already been run without finding this 63bit 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 20071218 3 curves, B1=50000, B2=5000000 by "Sturle Sunde" on 20081013 3 curves, B1=50000, B2=5000000 by "Sturle Sunde" on 20090221 3 curves, B1=50000, B2=5000000 by "Tapio Rajala" on 20090726 3 curves, B1=50000, B2=5000000 by "SubPrime" on 20091108 3 curves, B1=50000, B2=5000000 by "James Hintz" on 20100611 3 curves, B1=50000, B2=5000000 by "Bruce" on 20110223 1 curve, B1=50000, B2=5000000 by "Oscar Ã–stlin" on 20111119 3 curves, B1=50000, B2=5000000 by "James Hintz" on 20120410 3 curves, B1=50000, B2=5000000 by "OS1" on 20121030 
20130110, 23:37  #2 
Aug 2010
Kansas
547 Posts 
FWIW, P1 would take FOREVER to find this, since its a prime k.
I lack sufficient understanding to answer the ECM question, however. 
20130111, 00:01  #3 
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 89<O<88
3·29·83 Posts 
According to the well known GMPECM estimates, this is the ECM work data in that range:
Code:
t B1 standard curves BrentSuyama curves 20 11e3 74 74 25 5e4 221 214 30 25e4 453 430 35 1e6 984 904 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). Last fiddled with by Dubslow on 20130111 at 00:03 Reason: I accidentally a word 
20130111, 13:50  #4 
Apr 2004
Russia
2×3 Posts 
If a big number has a factor between 2^{62} and 2^{63}, 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 63bit factor up to 0.99 you should run about 90 ECM curves. 
20130111, 16:31  #5  
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
3·1,979 Posts 
Quote:
The probability of finding a 20 digit factor with 74 curves at 11e3 is 1e^1 With 37 curves 1e^(1/2). With n curves 1e^(n/74) etc. 99% chance of a 20 digit factor is 341 curves. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Odds of Finding a Factor  Gordon  Factoring  18  20150920 20:33 
Probability of finding a factor  JuanTutors  Software  20  20040926 09:47 
Chances of finding a factor with ECM  smh  Factoring  16  20040330 18:49 
possibility of finding a factor  there_is_no_spoon  Math  10  20040311 20:05 
Probability of finding a factor in TF  eepiccolo  Math  4  20030607 05:56 