How much ECM does it take to find a given factor?

[geoff]

If I find a factor q of a mersenne number by any method, then I can calculate the minimum effort it would have taken to find the factor with the P-1 method by looking at the factors of q-1 and working out the minimum B1 and B2 bounds that would have been required.

Is there a similar way to calculate how much ECM effort would have been required to find the factor?

[philmoore]

Originally Posted by geoff

Is there a similar way to calculate how much ECM effort would have been required to find the factor?

Look near the bottom of the ECMNET page at:
http://www.loria.fr/~zimmerma/records/ecmnet.html
It lists the expected number of curves which would be run to find various sized factors. Of course, a bit of luck is also involved.

[geoff]

Originally Posted by philmoore

It lists the expected number of curves which would be run to find various sized factors.

That table would apply even if I didn't know the factor in advance, but If I knew the actual factor it seems like I have more information so I should be able to make a better estimate. But maybe that intutition is wrong?

What I was thinking of doing is going through the known factors in factors.cmp and for each one, trying to decide which method of trial factoring, P-1, or ECM would have (in hindsight) required the least amount of work.

[nfortino]

Originally Posted by geoff

That table would apply even if I didn't know the factor in advance, but If I knew the actual factor it seems like I have more information so I should be able to make a better estimate. But maybe that intutition is wrong?

The success or failure of the method in factoring the number depends not only on the number and the bounds, as is the case with the p-1 method, but also on the arbitrary choice of a curve. Because there is no one method of choosing curves that is superior to all others, most algorithms choose the curves randomly. Only after running so many curves with a certain bound will the program give up, or move to a higher bound. This randomness makes it impossible to determine how much work is required to find a factor. For more information, http://www.mersenneforum.org/showthread.php?t=194 contains a good basic explanation by philmoore of how the elliptic curve method works.

[philmoore]

You might find this posting useful:
http://www.mersenneforum.org/showpos...6&postcount=19
It contains a MAPLE program written by Richard McIntosh and submitted with his permission, for computing the probability that a given ECM curve will find a given factor. If you don't have access to MAPLE, it might not be too difficult to translate it into your favorite language provided you have a routine which will calculate dilogarithms. His paper clarifies that by a 40-digit factor, for example, he means a minimum sized 40-digit factor, i.e., about 10^39. If you input 40.5 digits for the size of the factor, his estimates are more in line with those listed on the ECMNET page. So given a factor, input log(factor)+1 as the number of digits, where log means base-10 logarithm. You also input stage 1 and stage 2 bounds, and the program outputs the probability that one curve run with those bounds will find a factor of the given number of digits. 1 divided by the probability gives the expected number of curves. Of course, running the expected number is no guarantee, you could find the factor zero, one, two, or more times, but on average, you would expect to find it once.

[akruppa]

I tried to port MacIntosh's program to Pari, lacking Maple. However, I hit a few problems. For example, a straightforward port of his rho function gives me rho(2.5)= 3.6984... - 2.8786...*I, which is totally not what I expect of a probability.

So I started from scratch. I've made a Pari script that computes the probability for ECM to find a factor of a given size. I use Dickman's rho function, but with two corrections: the sigma correction term mentioned by Knuth/Trabb Pardo, and a correction to get the density of smooth integers at around x, not between 1 and x. The first term is about +10%, the second -20% for typical B1 and factor sizes, so they should be included. I estimate the chance of a stage 2 factor much like William does in this thread. I also account for factors found by the Brent-Suyama extension, using something similar as the mu function but with the probability for Brent-Suyama to include the prime factored in.

The results are usually within a few percent of experimental counts, so I hope this script is useful for choosing good parameters for ECM.

The important function is ecmprob(B1,B2,N,nr,S). B1 and B2 should be clear, N is the approximate factor, nr is the number of points evaluated in stage 2 for Brent-Suyama, S is the degree of the Brent-Suyama function. For S-th powers, S should be positive, for degree S Dickson polynomials, S should be negative. The number of points in stage 2 is k*dF^2, where k and dF are reported by gmp-ecm witht the -v parameter at the start of stage 2.

Example: how many curves does it take on average to find a p35 with gmp-ecm's default parameters for B1=1M?

First get gmp-ecm's parameters:

$echo 65537 | ecm5 -v 1e6-1e6
GMP-ECM 5.0.3 [powered by GMP 4.1.2] [ECM]
Input number is 65537 (5 digits)
Using special division for factor of 2^16+1
Using B1=1000000, B2=839549780, polynomial Dickson(6), sigma=2157207190
a=51553
starting point: x=19319
Step 1 took 0ms
x=19319
B2'=948726240 k=5 b2=189560910 d=43890 dF=4320
Initializing table of differences for F took 0ms
Found factor while computing F[49]
Step 2 took 20ms for 0 muls
********** Factor found in step 2: 65537
Found input number N

So gmp-ecm internally uses B2=948726240, k=5, dF=4320 and S=-6 (Dickson(6))

ecmprob tells us

? \rrho.gp
? ecmprob(1000000,948726240,sqrt(10)*10^34,5*4320^2,-6)
%5 = 0.0009601784546838897811362317141
? 1/%
%6 = 1041.473066930272122308814268
?

So we can expect ~1041 curves to find the p35 with these parameters. With S-th power as the Brent-Suyama function instead, we'd get 1046. With Dickson(3), 1080. With no Brent-Suyama (S=0), 1138. With no Brent-Suyama and B2=100M, 1902, etc..

A future version of gmp-ecm will probably include this and print the probability of success for different factor sizes with given parameters.

If you don't have Pari, you can use the Pari Calculator. Cut and paste the complete script into the calculator, but remove the two occurrances of the word "evaluating/ed" in the comments first! The calculator does not like them, obscuring them did not help. Add the call of ecmprob() or 1./ecmprob() to the end of the script. There'll be a bunch of questionmarks printed, but the correct result is there, too.

Hope this helps,
Alex