ECM Runtime and F20

[D. B. Staple]

Hello everyone,

I am wondering how the runtime of a single curve in the ECM scales in practice with N, B1, and B2.

I know from Silverman and Wagstaff's 1993 paper that the total runtime scales for constant factor size with the time for a single multiplication modulo N. For large N using FFT etc. multiplication I suppose this means the runtime of a single should go with log_2(N) for fixed B1 and B2.

For fixed N, runtime of a single curve seems to scale linearly with B1, which seems reasonable from my understanding of the algorithm.

Also, as long as a reasonable size is taken for B2 the runtime of 1 curve seems to be roughly independent of B2, with some optimal value of B2 as given in Zimmerman's table.

Have I got these three scalings roughly correct?

Finally one more question: what are some runtimes for single curves on the Fermat numbers? In particular I am wondering how long curves with B1=10^6 and B1=3*10^6 take on F20 (and what I should expect for 11*10^6).

Answers to any of these questions would be greatly appreciated,

Thanks,

Doug

[D. B. Staple]

I should have mentioned that the thread "Factoring F14" thread provides a partial answer to my performance on Fermat numbers question:

digits             b1              b2   k  mem  stage 1 ms  stage 2 ms
    35      1,000,000     839,549,780   5  249   1,247,434     963,127
    40      3,000,000   4,016,636,514   5  544   3,756,443   2,741,624
    45     11,000,000  25,577,181,640  20  679  13,831,555  11,372,366

I am still curious about the scaling though; the way I understand it running a single curve on F_n with n>14 should take on the order of 2^(n-14) times as long as the above calculations at the same B1 and default B2; but I'm not sure of this.

Has anyone in particular ran curves on F20?

[philmoore]

[Fri Sep 29 10:45:27 2006]
2^1048576+1 completed 5 ECM curves, B1=1000000, B2=100000000

These 5 curves took about 10 days on an Athlon system, 1400 MHz. My guess is that they would have taken about 1/3 of the time on a 3000 MHz Pentium processor.

Your scaling assumption sounds roughly correct, but from F14 to around F17, running time seems to more than double, sometimes tripling even, as you double the exponent. I don't know why, but I'm guessing that it may have something to do with cache utilization. Does anyone else have an opinion on this, or some hard data? Once we get to large numbers, the doubling approximation seems to hold, at least for stage 1, although stage 2 sometimes takes a hit because of main memory limitations.

[ATH]

I did a small speedtest 2 years ago: http://www.mersenneforum.org/showthread.php?t=4223

Original data: ECM.txt

Data in Excel where I did regression analysis: ECM.xls

Regression formulas: ECMregression.txt

step1:
When B1 is constant: time=constant*digits^1.7
When n is constant: time=constant*B1
Step1 conclusion: time = constant*B1*digits^1.7

step2:
When B2 is constant: time=constant*digits^1.2
When n is constant: time=constant*B2^0.6
step2 conclusion: time=constant*B2^0.6*digits^1.2

Offcourse this will hold less and less when you get to very high B1/B2 or n when memory becomes a problem.

[Andi47]

Originally Posted by ATH

I did a small speedtest 2 years ago: http://www.mersenneforum.org/showthread.php?t=4223

Original data: ECM.txt

Data in Excel where I did regression analysis: ECM.xls

Regression formulas: ECMregression.txt

step1:
When B1 is constant: time=constant*digits^1.7
When n is constant: time=constant*B1
Step1 conclusion: time = constant*B1*digits^1.7

step2:
When B2 is constant: time=constant*digits^1.2
When n is constant: time=constant*B2^0.6
step2 conclusion: time=constant*B2^0.6*digits^1.2

Offcourse this will hold less and less when you get to very high B1/B2 or n when memory becomes a problem.

Have you also done similar speedtests for p-1 and p+1?

[R.D. Silverman]

Originally Posted by Andi47

Have you also done similar speedtests for p-1 and p+1?

They will be MUCH faster than a single ECM curve.

[D. B. Staple]

Thanks everyone for your replies and comments. This gives me a good feeling for the subject. I will run some of my own calculations on F20,
as well as (properly) (re)read Silverman and Wagstaff's paper, and share any insight I garnish, if it is anything beyond what you all have said here.

[ATH]

Originally Posted by Andi47

Have you also done similar speedtests for p-1 and p+1?

I did some new tests of ECM, p-1 and p+1 with GMP-ECM 6.1.3 on GMP 4.2.2 on 3 different computers: p4 Northwood 2.4 Ghz 1Gb ram, p4 Prescott 3.4 Ghz 2Gb ram, Athlon XP 2200+ 1.80 Ghz 1Gb ram.

ECM: athlonECM.xls athlonECMregression.txt p4nECM.xls p4nECMregression.txt p4pECM.xls p4pECMregression.txt
P-1: athlonP-1.xls athlonP-1regression.txt p4nP-1.xls p4nP-1regression.txt p4pP-1.xls p4pP-1regression.txt
P+1: athlonP+1.xls athlonP+1regression.txt p4nP+1.xls p4nP+1regression.txt p4pP+1.xls p4pP+1regression.txt

ECM:
Ath: step1: time=constant*B1*digits^1.63 step2: time=constant*B2^0.63*digits^1.3
P4N: step1: time=constant*B1*digits^1.75 step2: time=constant*B2^0.63*digits^1.3
P4P: step1: time=constant*B1*digits^1.71 step2: time=constant*B2^0.63*digits^1.4

P-1:
Ath: step1: time=constant*B1*digits^1.6 step2: time=constant*B2^0.6*digits^1.3
P4N: step1: time=constant*B1*digits^1.7 step2: time=constant*B2^0.6*digits^1.4
P4P: step1: time=constant*B1*digits^1.7 step2: time=constant*B2^0.62*digits^1.35

Alot bigger variation on the exponent on the digits for P-1 than for ECM, ranging from 1.54 to 1.68 for athlon step1 and 1.29 to 1.45 for athlon step2, same kind of variation for the 2 other computers. Probably some of it caused by P-1 being so much faster than ECM that many of the timings are so small that random fluxuation plays a bigger role.

P+1:
Ath: step1: time=constant*B1*digits^1.59 step2: time=constant*B2^0.64*digits^1.3
P4N: step1: time=constant*B1*digits^1.70 step2: time=constant*B2^0.64*digits^1.3
P4P: step1: time=constant*B1*digits^1.67 step2: time=constant*B2^0.64*digits^1.35

Almost as low variation on exponents in P+1 as on ECM in step1, but higher variation like in P-1 in step2.


Looking at the timings ECM is about 9-10 times slower than P-1 at the same B1/B2 and 5-6 times slower than P+1, which fits with the advice in GMP-ECM readme to run P-1 with 10*B1 and P+1 with 5*B1, where B1 is the B1-value you use for ECM at each factor level.

[jasong]

It might be a good idea to take a bit of post 8, and give it it's own Sickey thread in the GMP-ECM forum.

Just my opinion. :)

[D. B. Staple]

[Fri Sep 29 10:45:27 2006]
2^1048576+1 completed 5 ECM curves, B1=1000000, B2=100000000

These 5 curves took about 10 days on an Athlon system, 1400 MHz.

For some reason I am getting nowhere near the performance that you have quoted here. I am using the newest versions of GMP and GMP-ECM, and have run the tune programs for both; this is on a 2.8 GHz Pentium 4. I call my program with the following command:

echo "2^(2^20)+1" | ./ecm -power 1 -maxmem 2048 -v 1000000

Which produces output along the lines of:

GMP-ECM 6.1.3 [powered by GMP 4.2.2] [ECM]
Input number is 2^(2^20)+1 (315653 digits)
Using B1=1000000, B2=904700226, polynomial x^1, sigma=2813888680
dF=128, k=5933, d=1020, d2=7, i0=974
Expected number of curves to find a factor of n digits:
20      25      30      35      40      45      50      55      60      65
5       21      130     1014    9706    110526  1461187 2.2e+07 3.7e+08 7.2e+09
Step 1 took 273197586ms
Estimated memory usage: 720M
... Lots of timing data removed here ...
Step 2 took 432207265ms

Now my value for B2 was ~9 times the value that you used, but even just my stage one timing of 273197586ms = ~3.16 days is way too high judging from what you have said. The only explainations I have thought of so far are:
(a) the verbose option is causing gmp-ecm to spend a lot of time doing timings etc.
(b) gmp-ecm is not nearly as fast as mprime for numbers of this size
(c) I have somehow made a serious mistake with the software

Does anyway have an explanation for what I have found?

[R.D. Silverman]

Originally Posted by D. B. Staple

<snip>

Step 2 took 432207265ms
[/code]Now my value for B2 was ~9 times the value that you used, but even just my stage one timing of 273197586ms = ~3.16 days is way too high judging from what you have said. The only explainations I have thought of so far are:
(a) the verbose option is causing gmp-ecm to spend a lot of time doing timings etc.
(b) gmp-ecm is not nearly as fast as mprime for numbers of this size
(c) I have somehow made a serious mistake with the software

Does anyway have an explanation for what I have found?

P95 will be a lot faster in stage 1 than GMP-ECM.
GMP-ECM will be faster in stage 2.