20040127, 00:54  #1 
Mar 2003
New Zealand
13·89 Posts 
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 P1 method by looking at the factors of q1 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? 
20040127, 16:27  #2  
"Phil"
Sep 2002
Tracktown, U.S.A.
10001100000_{2} Posts 
Quote:
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. 

20040128, 01:03  #3  
Mar 2003
New Zealand
13×89 Posts 
Quote:
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, P1, or ECM would have (in hindsight) required the least amount of work. 

20040128, 01:48  #4  
Nov 2003
3·5·11 Posts 
Quote:


20040128, 18:00  #5 
"Phil"
Sep 2002
Tracktown, U.S.A.
1120_{10} Posts 
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 40digit factor, for example, he means a minimum sized 40digit 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 base10 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. 
20040929, 20:14  #6  
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
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 BrentSuyama extension, using something similar as the mu function but with the probability for BrentSuyama 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 BrentSuyama, S is the degree of the BrentSuyama function. For Sth 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 gmpecm witht the v parameter at the start of stage 2. Example: how many curves does it take on average to find a p35 with gmpecm's default parameters for B1=1M? First get gmpecm's parameters: Quote:
ecmprob tells us Quote:
A future version of gmpecm 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 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Can Pollard Rho cycles be used to find a factor?  wwf  Factoring  26  20130930 04:24 
PFGW can't find a small factor.  Arkadiusz  Software  7  20130218 12:43 
Chance to find an ndigit factor with ECM  RedGolpe  Factoring  4  20070323 15:24 
Where I find the best program to it factor keys? I use AMD.  chrow  Factoring  5  20040219 10:15 
How large a factor can P1 testing find ?  dsouza123  Software  3  20031211 00:48 