20101118, 02:36  #1 
Apr 2010
Over the rainbow
2×3×5×79 Posts 
queestion about ecmgmp
hi.
I'm trying to learn the rope of ECMgmp software I know (understood rather) that, for a proper chance to find a factor, you have to have a phase 1 and a phase 2 or equal lengh. 1) ecm c 5 2e2 1e4 (phase 1 and 2 around 1.5 sec) 2) ecm c 5 1e0 5e4 (phase 1 almost instand, phase 2 3 secs) for a 8500 digits composite wich one of the 2 has a better chance to find a factor? 
20101118, 03:14  #2 
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
17·251 Posts 
Add the v (verbose) argument to print out a lot more information. From the output of how many curves you can expect to run before you find a factor of x digits, and then later how much time that should take, you can see which of different combinations has a better chance to find a factor either per curve or in a given time.
There are common levels to search for factors of a given size, such as 430 curves with B1=25e4 (250000) for 30 digit factors, that were once calculated to be the most efficient. What is best for your machine is best determined by some experimentation to see what sort of B1 values make for the lowest expected time for various factor digit sizes. Note that GMPECM can automatically make good choices for B2 values by leaving the B2 blank. Also note that an 8500 digit composite, unless it's specially constructed to have only small factors, is very unlikely to be fully factored by ECM in any reasonable amount of time (even years). Factors under 30 digits are pretty easy to find, and from there it gets harder and harder, such that 6070+ digits are the top 10 ECM finds for the year. For some more information, including much of the math behind it, see http://mersennewiki.org/index.php/Elliptic_curve_method 
20101118, 03:24  #3 
Apr 2010
Over the rainbow
2370_{10} Posts 
my goal there ,is not to fully factor those composite. It is to find the most factor, in the less time possible. (and i a m aware of the t switch).
As I am a regular contributor of aliquot sequence, i'm aware of the number of curve I should run.I'm just asking what is the best method for large number : a similar lenght step 1 and 2 or a nonexistent step 1 and a 'twice long' B2. edit : nevermind, since step 2 require a point found in step 1, it is best to use equal lenght step1 and 2 Last fiddled with by firejuggler on 20101118 at 03:38 
20101118, 15:53  #4  
Nov 2003
2^{2}·5·373 Posts 
Quote:
"most factors in least time possible" is nonsensical. The least time possible is 0. OTOH, you can select parameters to either maximize the probability of finding a factor in any given fixed amount of time, or you can select parameters to maximize the probability of finding a factor per unit time. In the latter case the amount of time spent is not bounded. Read my joint paper with Sam Wagstaff Jr: A Practical Analysis of ECM It was published in Mathematics of Computation. 

20101118, 16:37  #5 
Jun 2003
13×359 Posts 
A question for Bob.
In your paper, the conclusion that time spent in stage 1 and stage 2 should be roughly the same for optimal performance is based on the assumption that stage 2 time is proportional to B2. Is my understanding correct? If so, how does the fact that the current GMPECM stage 2 is _not_ proportional to B2, change that conclusion? 
20101118, 17:16  #6  
Jun 2005
lehigh.edu
2^{10} Posts 
Quote:
performs. The program analyzed in SilvermanWagstaff (ie., Peter Montgomery's 1987 program) was far better in step2 than previous code, as they describe. I first started with one of Peter's binaries of the 1987 version, which he circulated after he had his new ecm/fft, which had waybetteryet step2. Compare the curve counts in Bob's paper with the ones in Peter's thesis; totally different, not really comparable optimizations. The "rule" about equal times is NOT a rule. In particular, gmpecm has step2 performance that is closer to ecm/fft (except more portable, Peter's was based on MIPS/IRIX assembly code) than to Peter's earlier 1987 version. Bruce 

20101118, 17:17  #7  
Nov 2003
2^{2}·5·373 Posts 
Quote:
stage 2 time is proportional to B2. Suppose stage 2 is K times as fast as stage 1. That is to say, if we take step 1 to B1 in time t0, then we can take step 2 to K*B1 also in time t0. The optimal B2 limit is then K*B1. This will maximize the probability of success per unit time. If we use an FFTbased step 2, then we can take step 2 to limit B1^2 (up to a constant multiple that is implementation dependent) in the same time that it took to take step 1 to B1. At the time I wrote the paper, Peter Montgomery's Sparc code for ECM was the fastest known to me. It was not FFTbased for step 2, but it did achieve K = 100 (which is an often quoted value). 

20101118, 17:26  #8  
Nov 2003
7460_{10} Posts 
Quote:
Let me add that certain assumptions made then are not applicable now. The main assumption (unstated) then is that you use the same machine for step 1 and step 2. Now, (e.g. the work at EPFL) step 1 is/can be done on machines with special MP hardware, while step 2 is/can be done on other machines with large memory. 

20101118, 23:34  #9 
Nov 2003
16444_{8} Posts 

20101118, 23:36  #10 
Jun 2003
4667_{10} Posts 

20101119, 02:11  #11 
Jun 2003
13·359 Posts 
Ok. Second attempt. Does the analysis require that K be a constant for a given implementation and number, but for different B1?
So K is a function of B1 in this case, right? And it doesn't affect the conclusion of the analysis? 