mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2004-01-27, 00:54   #1
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

13×89 Posts
Default How much ECM does it take to find a given factor?

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?
geoff is offline   Reply With Quote
Old 2004-01-27, 16:27   #2
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

1,117 Posts
Default

Quote:
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.
philmoore is offline   Reply With Quote
Old 2004-01-28, 01:03   #3
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

115710 Posts
Default

Quote:
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.
geoff is offline   Reply With Quote
Old 2004-01-28, 01:48   #4
nfortino
 
nfortino's Avatar
 
Nov 2003

101001012 Posts
Default

Quote:
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.
nfortino is offline   Reply With Quote
Old 2004-01-28, 18:00   #5
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

1,117 Posts
Default

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.
philmoore is offline   Reply With Quote
Old 2004-09-29, 20:14   #6
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

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:
Quote:
$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
Quote:
? \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
Attached Files
File Type: zip rho.zip (3.1 KB, 172 views)
akruppa is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Can Pollard Rho cycles be used to find a factor? wwf Factoring 26 2013-09-30 04:24
PFGW can't find a small factor. Arkadiusz Software 7 2013-02-18 12:43
Chance to find an n-digit factor with ECM RedGolpe Factoring 4 2007-03-23 15:24
Where I find the best program to it factor keys? I use AMD. chrow Factoring 5 2004-02-19 10:15
How large a factor can P-1 testing find ? dsouza123 Software 3 2003-12-11 00:48

All times are UTC. The time now is 11:21.

Sun Sep 27 11:21:20 UTC 2020 up 17 days, 8:32, 0 users, load averages: 1.53, 1.60, 1.54

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.