Optimizing step 2 of ECM on Prime95

[alpertron]

Just to satisfy my curiosity, I downloaded the Prime95 source files and started to read the file ecm.c, where ECM is implemented.

It is not completely clear to me, but it appears that the code is using 8 multiples of the point found at the end of step 1 in the table used in step 2 when the modulus is 30 (all positive integers coprime to 30 and less than it). But only 4 multiples are enough, thus needing half the memory and making it twice as fast.

Please read the text I wrote on More detailed explanation section of ECM on MersenneWiki.

[Prime95]

IIRC, prime95 steps through the B1 to B2 range in multiples of 60 when the modulus is 30.

P.S. You are very brave to be looking in the ecm source code!

[alpertron]

In that case the optimization is already done.

What about the other optimization I wrote on MersenneWiki (multiplying the coordinates of the points where C+60k+t and C+60k-t are not both composite)? Using this, the step 2 speed almost doubled in my ECM applet.

[Prime95]

That should be implemented too

[alpertron]

OK. I've seen that code on stage 2, using the sieve() function to find the primes.

Of course the comment on line 2762 should be Do the m to m+D range.