New features in Prime95 v22.9

[guido72]

Hi all!
I've read last undoc.txt and I've seen that "Alexander Kruppa wrote some code that allows the output of ECM stage 1 to be passed to Paul Zimmermann's more efficient GMP-ECM stage 2. This program is usually faster in stage 1."
Is this code already embedded in Prime95 ones or do you have to download it somewere? "This program" means "Prime95", doesn't it?
Regards

[akruppa]

The code to print the number to be factored, residue and sigma at the end of stage 1 is included in Prime95/mprime. If you add

GmpEcmHook=1

to your prime.ini file and run ECM curves with B2 set between anywhere 1 and B1 (so that Prime95 does not do a stage 2), a line like

N=0x[...]; QX=0x[...]; SIGMA=0x[...]

is written to results.txt for each curve computed by Prime95. This info can be fed into gmp-ecm which will compute stage 2 for that curve then.

However, the normal gmp-ecm 4c is a little awkward for that purpose: if you specify a starting point on the curve (i.e., QX), it wants the "A" parameter to specify the curve, not SIGMA. And it can't read the N and QX values in hex. (You can get the value of A if you run a dummy curve (B1=0) in gmp-ecm with the -v option and sigma specified)

I've patched gmp-ecm 4c to make all that more convenient and I've asked Paul Zimmermann just now whether he would rather include the changes in a new release of gmp-ecm or let me offer the patched version.

Once that is decided, I hope that the new code will be available very shortly.

Alex

[guido72]

Alles Klar, Alex!
Vielen Dank.
Herzliche Gr?ße aus Italien.
Guido

[patrik]

I spent yesterday trying to do stage 1 prime95 and stage 2 in ecm-gmp 5.0, but ecm still keeps doing stage 1.

I've looked into the source files of ecm, and there is some code in resume.c
[code:1] if (have_n && have_sigma)

{
*method = EC_METHOD;
*b1 = 1.0;
strcpy (program, "Prime95");
return 1;
}
[/code:1]which sets B1done (how far B1 was taken in stage 1) to 1. Then in ecm.c there is[code:1] if (B1 > B1done)
youpi = ecm_stage1 (f, P.x, P.A, modulus, B1, B1done);
[/code:1] where the stage 1 is called. (B1done is *b1 above.) This is the reason stage 1 gets done again.

In resume.c, is *b1=1.0 intended to be a flag saying that stage1 should be skipped? E.g. "if (B1 > B1done && B1done != 1.0)" instead? Or are things more complicated? In save files from ecm, there is a number called X, while in files from prime95, it is called QX. Do they contain any information of B1?

Maybe I shouldn't change details when I don't understand the main ideas.

[garo]

There was a post yesterday by Alex Kruppa on the mersenne mailing list . I am quoting it in it's entireity. It answers all your questions.

Hi,

gmp-ecm version 5 can read ECM residues written by Prime95 to perform
stage 2 on them. Stage 2 is asymptotically faster in gmp-ecm, but
Prime95 has a much faster multiplication for large numbers, so this
feature is mostly interesting for relatively small numbers (i.e. of a
few
thousand bits) that are to be factored with a large stage 2 limit.
Another
feature is that the B2 value in gmp-ecm is not limited to 2^32, so you
may
take stage 2 limit to much higher values than Prime95 currently
supports.

In order to be able to resume ECM residues from Prime95 (version 22.9 or
later), you will first have to set the GmpEcmHook option (described in
undoc.txt) in prime.ini. Simply add the line

GmpEcmHook=1

This will cause Prime95 to write the residues from the end of stage 1 to
results.txt if no stage 2 is performed.

These residues in results.txt can be read into gmp-ecm with the -resume
option to do stage 2.

Example: Richard Brent's factorization of F10
(remeber to put the smaller factors 45592577 and 6487031809 into
lowp.txt
if you want to try this example yourself)

workdodo.ini :

ECM=1024,314263,1,1,0,14152267,1,20

This computes the lucky curve with sigma=14152267 and a stage 1 bound
of 314263. Note that B2 is set to 1, so that Prime95 will not do a stage
2 but will write the residue instead.

Running Prime95 (or mprime) now outputs

Mersenne number primality test program version 22.12
ECM on P1024: curve #1 with s=14152267, B1=314263, B2=314263
Stage 1 complete. 8133791 transforms, 1 modular inverses. Time: 13.603
sec.
Stage 1 GCD complete. Time: 0.000 sec.
There are no more exponents to test.
Please send the results.txt file to woltman@alum.mit.edu
Contact the PrimeNet server for more exponents.

The results.txt file contains

[Wed Feb 26 19:15:13 2003]
N=0x3E(... deleted ...)001; QX=0x275(...deleted...)802; SIGMA=14152267
UID: akruppa, P1024 completed 1 ECM curves, B1=314263, B2=314263

The stage 2 for this residue can be computed with gmp-ecm 5 by running

ecm -resume results.txt 1 314263-10000000

which outputs

GMP-ECM 5.0 [powered by GMP 4.1] [ECM]
Save file line has no equal sign after: [Wed Feb 26 19:
Resuming ECM residue saved with Prime95
Input number is 607(... deleted ...)569 (291 digits)
Using B1=1, B2=314263-10000000, polynomial x^1, sigma=14152267
Step 1 took 0ms
Step 2 took 2450ms
********** Factor found in step 2:
4659775785220018543264560743076778192897
Found probable prime factor of 40 digits:
4659775785220018543264560743076778192897
Probable prime cofactor 130(... deleted ...)577 has 252 digits
Save file line has no equal sign after: UID: akruppa, P

The factor is being found. (Gmp-ecm complains about the lines in
results.txt it does not understand, but the residues should be processed
correctly)

The parameters to gmp-ecm are:

-resume <filename>
Which file to read the residues from

1
The stage 1 limit, which we set to 1 because we have already done the
stage 1 computations with Prime95

314263-10000000
The stage 2 range. Prime95 did stage 1 with B1=314263, so we tell
gmp-ecm to do stage 2 from that point on, up to 10000000. The lower
limit of the stage 2 range should always be set to the B1 value Prime95
used, the upper limit is the effective B2 value for the ECM curve.


If you would like to do, say, 100 curves on F12 with B1=44000000, you
should have in worktodo.ini

ECM=4096,44000000,1,100,0,0,1

After Prime95 has completed the stage 1 for the 100 curves, you can
resume the residues in results.txt with

ecm -resume results.txt 1 44000000-184367799127

Note: 184367799127 is the default value for gmp-ecm with B1=44M. You
may want to lower it so that the time spent in Prime95 and gmp-ecm per
curve is roughly the same.

Note 2: remember to remove or rename results.txt after running it
through gmp-ecm, or the next time around it will process the same
residues
again.

Happy factoring, and good luck!

Alex