mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2012-08-21, 04:48   #1
Walter Nissen
 
Walter Nissen's Avatar
 
Nov 2006
Terra

2·3·13 Posts
Question 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 GMP-ECM.
Why do the second derivatives change sign ?
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. ?
Walter Nissen is offline   Reply With Quote
Old 2012-08-21, 07:06   #2
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

23×797 Posts
Default

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 sub-exponential in the number of digits of the factor.

These figures from gmp-ecm come from the mathematics rather than from computer technology - you get slightly different ones if you optimise measured runtime rather than number of curves
fivemack is offline   Reply With Quote
Old 2012-08-21, 07:44   #3
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×29×83 Posts
Default

Quote:
Originally Posted by fivemack View Post
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 sub-exponential in the number of digits of the factor.

These figures from gmp-ecm come from the mathematics rather than from computer technology - you get slightly different ones if you optimise measured runtime rather than number of curves
No, he means this: Take, e.g., B1:

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).
Dubslow is offline   Reply With Quote
Old 2012-08-21, 09:20   #4
pinhodecarlos
 
pinhodecarlos's Avatar
 
"Carlos Pinho"
Oct 2011
Milton Keynes, UK

10010101010012 Posts
Default

ECM - elliptic curve factorization method
pinhodecarlos is offline   Reply With Quote
Old 2012-08-21, 10:00   #5
axn
 
axn's Avatar
 
Jun 2003

10010101101102 Posts
Default

Quote:
Originally Posted by pinhodecarlos View Post
ECM - elliptic curve factorization method
?
axn is offline   Reply With Quote
Old 2012-08-26, 00:07   #6
Walter Nissen
 
Walter Nissen's Avatar
 
Nov 2006
Terra

2×3×13 Posts
Question cites ?

Quote:
Originally Posted by pinhodecarlos View Post
ECM - elliptic curve factorization method
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
Splicing the tables together introduces a minor inconsistency .
32804 would be 32741 , if earlier 69471 were used .

Last fiddled with by Walter Nissen on 2012-08-26 at 00:14 Reason: restored missing column label
Walter Nissen is offline   Reply With Quote
Old 2012-08-26, 16:11   #7
rcv
 
Dec 2011

8F16 Posts
Default

Quote:
Originally Posted by Walter Nissen View Post
... what parts of what papers do I need to read ...?
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 445-462.

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.
rcv is offline   Reply With Quote
Old 2012-08-27, 14:59   #8
Walter Nissen
 
Walter Nissen's Avatar
 
Nov 2006
Terra

2·3·13 Posts
Question

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 .
Walter Nissen is offline   Reply With Quote
Old 2012-09-01, 23:07   #9
Walter Nissen
 
Walter Nissen's Avatar
 
Nov 2006
Terra

2·3·13 Posts
Question

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. ?
Walter Nissen is offline   Reply With Quote
Old 2012-09-02, 05:43   #10
rcv
 
Dec 2011

100011112 Posts
Default

@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
rcv is offline   Reply With Quote
Old 2012-09-02, 06:33   #11
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

160658 Posts
Default

Quote:
Originally Posted by rcv View Post
@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.
I'm pretty sure this is what he meant. He didn't say it wasn't
Quote:
Originally Posted by Dubslow View Post
No, he means this: Take, e.g., B1:

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).
Dubslow is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
ECM - why 3 curves? James Heinrich PrimeNet 3 2017-11-14 13:59
JKL-ECM: ECM using Hessian curves CRGreathouse Software 1 2017-09-06 15:39
Need help with elliptic curves... WraithX Math 12 2010-09-29 09:34
Curves needed henryzz GMP-ECM 3 2007-12-21 16:13
Elliptic curves in NFS otkachalka Factoring 5 2005-11-20 12:22

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

Tue Dec 1 21:10:46 UTC 2020 up 82 days, 18:21, 2 users, load averages: 1.81, 1.96, 2.16

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.