ECM Stage 2 RAM

[axn]

Originally Posted by Gordon

Step 1 took 3847484ms
Step 2 took 1217010ms

Interesting.
1) Why is Step 1 running again?
2) How much time would P95 have taken on this B2?

[GP2]

Originally Posted by axn

Interesting.
1) Why is Step 1 running again?
2) How much time would P95 have taken on this B2?

Perhaps GMP-ECM's implementation of stage 2 uses a step 1 and a step 2. So it's not redoing stage 1, at least I hope not. The README file does refer to "stage 1" and "stage 2", so I don't think "step 1" is a synonym for "stage 1", unless they're very loose with their terminology.

I'm doing some ECM of small Wagstaff numbers up to t=40, and I get the same thing when using GMP-ECM to do stage 2 where stage 1 was done by mprime.

GMP-ECM is run with the -resume option specifying the output written by mprime to results.txt, where mprime used B1=B2 and the GmpEcmHook=1 setting in prime.txt. If it really is redoing stage 1, I hope someone will let me know how to avoid it...

Here's some sample verbose output:

GMP-ECM 7.0.4 [configured with GMP 6.0.0, --enable-asm-redc] [ECM]
Running on ip-***-***-***-***.us-east-2.compute.internal
Resuming ECM residue saved with Prime95
Input number is 0x4D591058893F231FBE69EBEF89B145E1B39711E4E2D33DA1F18BD2E8EA9BDD232321C5FC7FDA0190625DB92793F0433C69FB1B9D55E06CB2712F78F11CB2651238578856D7C38207B0B802860CD4027485E15F72053DF77AA0A6A3C3FF21048AAAD0EB867C49CAD28F57AAB9EA017C9520C4B5241 (281 digits)
Using special division for factor of 2^1063+1
Using B1=3000000, B2=5706890290, polynomial Dickson(6), sigma=0:4566259830273646
dF=16384, k=2, d=158340, d2=11, i0=8
Expected number of curves to find a factor of n digits:
35      40      45      50      55      60      65      70      75      80
324     2351    20272   201449  2247436 2.8e+07 3.9e+08 6e+09   1.1e+11 7.4e+15
Step 1 took 11982ms
Using 33 small primes for NTT
Estimated memory usage: 88.06MB
Initializing tables of differences for F took 11ms
Computing roots of F took 392ms
Building F from its roots took 620ms
Computing 1/F took 324ms
Initializing table of differences for G took 18ms
Computing roots of G took 367ms
Building G from its roots took 648ms
Computing roots of G took 368ms
Building G from its roots took 647ms
Computing G * H took 175ms
Reducing  G * H mod F took 169ms
Computing polyeval(F,G) took 1221ms
Computing product of all F(g_i) took 10ms
Step 2 took 5025ms

[PhilF]

Originally Posted by GP2

If it really is redoing stage 1, I hope someone will let me know how to avoid it...

I am getting ready to do some Fermat ECM factoring work, and I think I'll wait until you get a firm answer on that before I start.

I'm surprised the need to hook the two programs together in order to get the most efficiency still exists. Is there a reason the faster GMP-ECM stage 2 code has not been implemented in Prime95/mprime?

[GP2]

Hmm... so much for my theories about "step" vs. "stage".

I just tried running a curve where both stage 1 and stage 2 were done with GMP-ECM, and the whole thing actually ran faster than letting GMP-ECM resume the output of mprime's stage 1!

At least for this particular exponent. And that doesn't even include the time that mprime itself spent doing stage 1 (needlessly??).

The value of B2=5706890290 was automatically selected in both cases, and the 281-digit "Input number is" values are equal in both cases (specified as a hex number in the first example since that's how mprime outputs it, and specified as (2^1063+1)/3 divided by the two known factors in the second example below. So the only thing different in the two situations is a different sigma.

The command was:

echo "(2^1063+1)/3/114584129081/26210488518118323164267329859" | ecm -v 3000000

and the output was:

GMP-ECM 7.0.4 [configured with GMP 6.0.0, --enable-asm-redc] [ECM]
Running on ip-***-***-***-***.us-east-2.compute.internal
Input number is (2^1063+1)/3/114584129081/26210488518118323164267329859 (281 digits)
Using special division for factor of 2^1063+1
Using B1=3000000, B2=5706890290, polynomial Dickson(6), sigma=0:12915475272312803168
dF=16384, k=2, d=158340, d2=11, i0=8
Expected number of curves to find a factor of n digits:
35      40      45      50      55      60      65      70      75      80
324     2351    20272   201449  2247436 2.8e+07 3.9e+08 6e+09   1.1e+11 7.4e+15
Step 1 took 10870ms
Using 33 small primes for NTT
Estimated memory usage: 88.06MB
Initializing tables of differences for F took 10ms
Computing roots of F took 357ms
Building F from its roots took 570ms
Computing 1/F took 302ms
Initializing table of differences for G took 16ms
Computing roots of G took 335ms
Building G from its roots took 592ms
Computing roots of G took 336ms
Building G from its roots took 580ms
Computing G * H took 154ms
Reducing  G * H mod F took 164ms
Computing polyeval(F,G) took 1090ms
Computing product of all F(g_i) took 9ms
Step 2 took 4570ms
Expected time to find a factor of n digits:
35      40      45      50      55      60      65      70      75      80
1.39h   10.08h  3.62d   36.00d  1.10y   13.81y  192.57y 2937y   54485y  4e+09y
Peak memory usage: 130MB

[PhilF]

Do you have mprime set to limit the number of cores it can use? I'm also wondering if your results would be very different if the input number was millions of digits.

[GP2]

Originally Posted by PhilF

Do you have mprime set to limit the number of cores it can use? I'm also wondering if your results would be very different if the input number was millions of digits.

These are running on one-core virtual machines, so it's not an issue.

Also it shouldn't matter to gmp-ecm how many cores mprime used in stage 1. The input to ecm is just a number, it shouldn't matter how that number was arrived at.

Empirically, it's been reported that GMP-ECM works well only for small Mersenne exponents, under about 40k. So I don't think the millions-of-digits case would occur in practice.

[VBCurtis]

Originally Posted by PhilF

Do you have mprime set to limit the number of cores it can use? I'm also wondering if your results would be very different if the input number was millions of digits.

Yes, the outcome is quite different for large-large inputs!

GMP-ECM and mprime use very different methods for ECM computation. mprime (prime95) scales very well by input size, while GMP-ECM uses a stage 2 that's very very fast for small input sizes.

Below about 400(?) digits, GMP-ECM is faster in both stages. Above about 12000 digits (though Gordon above disagrees with this number!), mprime is faster for both stages. In between, the fastest method is to use mprime's fast stage1 code and GMP-ECM's fast-for-big-B2 stage 2. The set of users that care about inputs below 12000 digits is small, likely why the GMP-ECM stage 2 has never been incorporated into mprime.

[GP2]

I think I figured it out.

As mentioned before, if you want to do stage 1 with mprime/Prime95 and stage 2 wth GMP-ECM, first you need to run mprime/Prime95 with the line GmpEcmHook=1 in your prime.txt file, and you need to set B1 and B2 to the same value (say 3000000) in your ECM2= lines in your worktodo.txt file.

Then mprime/Prime95 will output a bunch of lines starting with N= into your results.txt file, instead of its normal output. If you specified 1000 ECM curves, then there will be 1000 lines with N=.

Note, if B1 and B2 aren't the same value in the worktodo.txt line, then GmpEcmHook=1 will be ignored and mprime/Prime95 will just do both stage 1 and stage 2 all by itself, and will output only the typical single line of the form "Mxxxx completed xxx ECM curves, B1=nnnnnnn, B2=nnnnnnnnn"

Then you feed that results.txt file to GMP-ECM. I don't know if you need to filter out all the lines that don't start with N=, probably GMP-ECM just ignores them. You do that with the command:

(assuming you used B1=3000000, change to whatever the actual value is)

ecm -resume results.txt 3000000-3000000 > my_output_file.txt

Then when it finishes, you search your my_output_file.txt (or whatever you called it) for lines that begin with:

********** Factor found in step

But the crucial thing is to specify the argument as 3000000-3000000 (meaning, do stage 1 for B1 from the range 3 million to 3 million, i.e. don't do it at all, but you need to specify the 3 million twice anyway so that B2 gets automatically sized appropriately). Of course, you can specify your own value for B2 if you don't want GMP-ECM's default calculated value. And change the "3 million" to whatever actual value of B1 you used in stage 1.

If you do that, then you get "Step 1 took 0 ms".

But if you just specify the argument as 3000000, as I was doing these past few weeks for ECM on small Wagstaff numbers, then it does stage 1 for B1 from 0 to 3 million, i.e., redoes the whole thing.

I hadn't done GMP-ECM for a long time, so I forgot about this nuance, and it's not actually very well documented, if at all.

TL;DR: when running GMP-ECM with -resume and you don't want it to redo stage 1, specify the B1 value as a range from itself to itself, with a hyphen in between, rather than just specifying it as a simple number, which will be interpreted as a range from 0 to that number.

[Gordon]

Originally Posted by axn

Interesting.
1) Why is Step 1 running again?
2) How much time would P95 have taken on this B2?

In answer to point 1 - that's my fault, it was early days of using gmp-ecm and I didn't know then that if I had stated the B1 value as

1000000-1000000

then it would have skipped redoing the stage 1. Learnt from that mistake early on :-)

as to point 2 I've got no idea.

[Gordon]

Originally Posted by GP2

Perhaps GMP-ECM's implementation of stage 2 uses a step 1 and a step 2. So it's not redoing stage 1, at least I hope not. The README file does refer to "stage 1" and "stage 2", so I don't think "step 1" is a synonym for "stage 1", unless they're very loose with their terminology.

I'm doing some ECM of small Wagstaff numbers up to t=40, and I get the same thing when using GMP-ECM to do stage 2 where stage 1 was done by mprime.

GMP-ECM is run with the -resume option specifying the output written by mprime to results.txt, where mprime used B1=B2 and the GmpEcmHook=1 setting in prime.txt. If it really is redoing stage 1, I hope someone will let me know how to avoid it...

[snip]

ecm -maxmem 14000 -resume results.txt 1000000-1000000 100000000 > newresults.txt

[axn]

Originally Posted by Gordon

In answer to point 1 - that's my fault, it was early days of using gmp-ecm and I didn't know then that if I had stated the B1 value as

1000000-1000000

then it would have skipped redoing the stage 1. Learnt from that mistake early on :-)

Cool

Originally Posted by Gordon

as to point 2 I've got no idea.

The reason I ask is that I suspect P95 will be (much) faster at that exponent size and that B2 level (smaller exponent and/or larger B2 will tilt it in favor of GMP-ECM). If you ever run similar ECMs in the future, it'll be definitely worthwhile to benchmark both options before you select which way to go.