Chance to find an n-digit factor with ECM

[RedGolpe]

I've been looking for the formula giving the chance to find a factor with n digits running a curve with B1=m in GMP-ECM 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?

[akruppa]

There isn't really a simple formula... unless a properly weighted integral of the Dickman rho function counts as "simple." GMP-ECM 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 GMP-ECM does (in fact the code in GMP-ECM 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

[RedGolpe]

Thank you. That was exactly what I was looking for.

[fivemack]

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 second-largest 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).

[R.D. Silverman]

Originally Posted by fivemack

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.

<snip>

[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;

<snip>

I suppose I could quantise and use a Bayesian approach;

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.