20060805, 21:58  #1 
Aug 2006
Monza, Italy
73 Posts 
Chance to find an ndigit factor with ECM
I've been looking for the formula giving the chance to find a factor with n digits running a curve with B1=m in GMPECM 6.0.1, but had no luck. I also tried to interpolate the results given with the verbose option on, but again I couldn't figure the correct formula. Anyone can help?

20060805, 22:44  #2 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
There isn't really a simple formula... unless a properly weighted integral of the Dickman rho function counts as "simple." GMPECM prints the probability of finding a factor of n decimal digits for n a multiple of five, 20≤n≤65. If you want accurate probabilities for different factor sizes, you could use the rho.gp script at
http://home.in.tum.de/~kruppa/rho.gp It does the same computations that the code in GMPECM does (in fact the code in GMPECM is a port of the Pari/GP script) and allows you to specify the factor size as you please. See the comments at the start of the script. Feel free to ask here if you have specific questions about the script. Alex 
20060806, 06:14  #3 
Aug 2006
Monza, Italy
73 Posts 
Thank you. That was exactly what I was looking for.

20070323, 15:07  #4 
(loop (#_fork))
Feb 2006
Cambridge, England
2×7×461 Posts 
Should I go on ECMing?
Suppose that I have a C110 on which I've run 100 curves at B1=10^7 without success.
I obviously now have some posterior information about the factors; by using rho.gp, I can see that it is very unlikely that there's a factor <10^30, and that there's about a 50% chance that I'd have missed a factor <10^35. I now have a choice. In 24 hours, I can guarantee to find with ggnfs any factor that there might be. Or I could run a thousand curves at 10^7, which would reasonably reliably find any factor <10^40, and might quickly pop up a factor <10^35, but if it finds nothing I still have to run the ggnfs. [I want to minimise expected time to solution. ggnfs takes 24 hours, one curve takes 90 seconds, so I should do the single curve if it has P>1/960 of finding a factor; if it succeeds I'm happy, if it doesn't succeed then I know the next curve has less chance of finding a factor] I suspect the right strategy now is to go straight to ggnfs; I don't think that 500 curves at 10^7, which would run for 12 hours, has as much as a 50% chance of finding the factor; that is, I believe that the probability that a C110 with no factor <10^32 has a smallest factor between 10^32 and 10^40 is less that 0.5. But I don't know how to go about computing that probability ... it may be in the current edition of Knuth volume 2, but I have the first edition of that volume and it's not there. I suppose I could quantise and use a Bayesian approach; what's a good reference to find what the prior probability distribution of the number of digits in the secondlargest factor of a C110 looks like? Then I just run Bayes's theorem 100 times using rho.gp as probability(factorises with one ECM@1E7 factor of N digits) to get what probability (factor of N digits does not factorise with 100 ECM@1e7), and then get a probability of success with the next curve as sum_N P(factor has N digits) P(one curve @1e7 factorises a number with a factor of N digits). 
20070323, 15:24  #5  
"Bob Silverman"
Nov 2003
North of Boston
1110101010100_{2} Posts 
Quote:
Read my joint paper with Sam Wagstaff: "A Practical Analysis of the Elliptic Curve Factoring Algorithm". This paper does indeed use Bayes' theorem to solve the problem of when to switch. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
New 70 digit factor  R.D. Silverman  Cunningham Tables  16  20160123 22:16 
DC chance to find Mersenne Prime  houding  PrimeNet  1  20140224 20:25 
73 digit ECM factor  akruppa  Factoring  103  20101127 20:51 
160 digit factor found of 366 digit (PRP1)  AntonVrba  Factoring  7  20051206 22:02 
How much ECM does it take to find a given factor?  geoff  Factoring  5  20040929 20:14 