20120821, 04:48  #1 
Nov 2006
Terra
2·3·13 Posts 
B1 and # curves for ECM
In the table in the readme , we find :
Code:
digits optimal B1 expected curves N(B1,B2,D) default poly 20 11e3 74 25 5e4 214 30 25e4 430 35 1e6 904 40 3e6 2350 45 11e6 4480 50 43e6 7553 55 11e7 17769 60 26e7 42017 65 85e7 69408 Table 1: optimal B1 and expected number of curves to find a factor of D digits with GMPECM. Does this come from the mathematics or is it from the details of the computer technology used to compute the estimates , such as available RAM , cache sizes at various levels , disk access times , etc. ? 
20120821, 07:06  #2 
(loop (#_fork))
Feb 2006
Cambridge, England
2·11·17^{2} Posts 
Which second derivatives are you talking about? If you mean 'why are plots of log(B1) against number of digits concave', that is a corollary to the expected runtime of ECM being subexponential in the number of digits of the factor.
These figures from gmpecm come from the mathematics rather than from computer technology  you get slightly different ones if you optimise measured runtime rather than number of curves 
20120821, 07:44  #3  
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 89<O<88
1C35_{16} Posts 
Quote:
11e3 5e4  ratio to previous 4.5 25e4  ratio to previous 5.0 1e6  ratio to previous 4.0 3e6  ratio to previous 3.0 11e6  ratio to previous 3.67 43e6  ratio to previous 3.91 If you plot those ratios, the second derivative (which should be zero) swings from positive to negative and back, without every really settling at zero. The same thing happens with necessary curves  the ratio changes for each digit jump. I've actually had this same question myself more than once (which is probably why I understood him). 

20120821, 09:20  #4 
"Carlos Pinho"
Oct 2011
Milton Keynes, UK
7·673 Posts 
ECM  elliptic curve factorization method

20120821, 10:00  #5 
Jun 2003
7·11·61 Posts 

20120826, 00:07  #6 
Nov 2006
Terra
2×3×13 Posts 
cites ?
Perhaps part of your post is an answer with a
quite serious intent . If so , what parts of what papers do I need to read to view this ellipticity for myself ? Extending the readme table using http://www.loria.fr/~zimmerma/records/ecm/params.html and computing some ratios and differences gives : Code:
digits B1 ratio curves diff ratio 20 11000 74 25 50000 4.55 214 140 2.89 30 250000 5. 430 216 2.01 35 1000000 4. 904 474 2.1 40 3000000 3. 2350 1446 2.6 45 11000000 3.67 4480 2130 1.91 50 43000000 3.91 7553 3073 1.69 55 110000000 2.56 17769 10216 2.35 60 260000000 2.36 42017 24248 2.36 65 850000000 3.26 69408 27391 1.65 70 2900000000 3.4 102212 32804 1.47 75 7600000000 2.62 188056 85844 1.84 80 25000000000 3.29 265557 77501 1.41 32804 would be 32741 , if earlier 69471 were used . Last fiddled with by Walter Nissen on 20120826 at 00:14 Reason: restored missing column label 
20120826, 16:11  #7 
Dec 2011
11·13 Posts 
Walter: I think the journal article you seek is "A Practical Analysis of the Elliptic Curve Factoring Algorithm", by Robert D. Silverman and Samuel S. Wagstaff, Jr., Mathematics of Computation, v61, n203, July 1993, pp 445462.
According to Table 3, a round B1 value for 40 digits might have been better chosen as about 4000000. As the paper points out, the curves are very flat where we are working. "Changes of +/ 10% in B1 can result in less than a 1% change in the global response surface..." So, at 40 digits, B1 is a little lower than perhaps it should be. But we do more curves to compensate. Disclaimer: The above referenced paper is, I believe, the primary basis by which curve choices are made. I don't necessarily agree with those choices. My own (unpublished) analysis, using some different assumptions, shows that we may be doing too many curves at each level. But that's a topic for another day. 
20120827, 14:59  #8 
Nov 2006
Terra
2×3×13 Posts 
Thanks much for your perceptive response .
Computing a couple more ratios ( of ratios ) here : In the B1 ratio column , the ratio of the largest ratio to the smallest ratio is more than 2.1 . In the # of curves ratio column , the ratio of the largest ratio to the smallest ratio is more than 2 . Their Figure 2. , albeit logarithmic , doesn't suggest such wide variation . There must be a lot of detail that doesn't appear in the paper , but I don't see any function in the paper which would produce changes in the sign of the second derivatives = the roller coasters . 
20120901, 23:07  #9 
Nov 2006
Terra
2·3·13 Posts 
http://www.mersenneforum.org/showthr...=11615&page=11
contains some informative messages from akruppa . The depth of my ignorance is such that I can't cite an example with specific digit sizes . So , I'll just make some up , which may be suitable , or not . I wouldn't expect optimal B1's to have the same effectiveness in finding p38's as p39's . Nor p39's as p40's . But it's not immediately apparent to me why the change in effectiveness from p38 to p39 might change in a different direction compared to that from p39 to p40 . Would we expect the same if instead of focusing on digit sizes of 20 , 25 , 30 , etc. , attention were paid to 20.5 , 25.5 , 30.5 , etc. ? Or 24.6 , 29.6 , 34.6 , etc. ? 
20120902, 05:43  #10 
Dec 2011
11×13 Posts 
@Walter: If my comments didn't help, then will you please make clear exactly what second derivatives are changing sign. Use specific numbers from published tables and *show us* the second derivatives that are changing.
@mod: Is it really necessary to randomly change the title of every thread in the forums? Perhaps it is my weak mind, but I don't read everything, and I can't keep track of the topics I'm following when thread titles change. ty 
20120902, 06:33  #11  
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 89<O<88
1110000110101_{2} Posts 
Quote:
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
ECM  why 3 curves?  James Heinrich  PrimeNet  3  20171114 13:59 
JKLECM: ECM using Hessian curves  CRGreathouse  Software  1  20170906 15:39 
Need help with elliptic curves...  WraithX  Math  12  20100929 09:34 
Curves needed  henryzz  GMPECM  3  20071221 16:13 
Elliptic curves in NFS  otkachalka  Factoring  5  20051120 12:22 