 mersenneforum.org how much ECM without finding an existing factor
 Register FAQ Search Today's Posts Mark Forums Read 2013-01-10, 23:34 #1 dbaugh   Aug 2005 112 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 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   2013-01-10, 23:37 #2 c10ck3r   Aug 2010 Kansas 547 Posts FWIW, P-1 would take FOREVER to find this, since its a prime k. I lack sufficient understanding to answer the ECM question, however.   2013-01-11, 00:01 #3 Dubslow Basketry That Evening!   "Bunslow the Bold" Jun 2011 40" means that there's a exp(-1) ~ 37% chance of having missed a 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). Last fiddled with by Dubslow on 2013-01-11 at 00:03 Reason: I accidentally a word   2013-01-11, 13:50 #4 Axon   Apr 2004 Russia 2×3 Posts If a big number has a factor between 262 and 263, 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.   2013-01-11, 16:31   #5
henryzz
Just call me Henry

"David"
Sep 2007
Liverpool (GMT/BST)

176016 Posts Quote:
 Originally Posted by Axon If a big number has a factor between 262 and 263, 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.  Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post Gordon Factoring 18 2015-09-20 20:33 JuanTutors Software 20 2004-09-26 09:47 smh Factoring 16 2004-03-30 18:49 there_is_no_spoon Math 10 2004-03-11 20:05 eepiccolo Math 4 2003-06-07 05:56

All times are UTC. The time now is 02:02.

Mon May 23 02:02:57 UTC 2022 up 39 days, 4 mins, 0 users, load averages: 1.02, 1.04, 1.10