ECM puzzle (hard)

[akruppa]

Note: do not attempt to solve this if you are unfamiliar with the internal workings of ECM and its implementations.

This is an oddity I stumbled upon while making a few more test cases for 2^n+-1 numbers for GMP-ECM with the GWNUM stage 1. It caused a bit of puzzlement between Dave and me on the developers mailing list, until Paul Zimmermann completely solved the mystery.


echo 33554520197234177 | ./ecm -sigma 2046841451 372 1

does not find the prime, but

echo 33554520197234177 | ./ecm -sigma 2046841451 373 1

does. However,

echo 33554520197234177 | ./ecm -sigma 2046841451 -go 373 372 1

does not. Why?


Alex

[akruppa]

I admit that this puzzle was a bit unfair, but I think the answer is interesting enough to post it anyways.

GMP-ECM (and Prime95 as well) use Montgomery's PRAC algorithm to multiply a point on the curve by a small integer, i.e. by the successive stage 1 primes. The PRAC algorithm ensures that at any time, when two multiples a*X and b*X of a point X are to be added to (a+b)*X during the addition chain, the difference (a-b)*X is already known. This is required for doing arithmetic using the Montgomery parameterisation of elliptic curves.

Since the group order of the curve with sigma=2046841451 is 2^2*3^5*5^2*13*23^2*59*83*131*313 and 23^2=529, the factor should be found if B1>=529, or if an extra factor of 23 "magically" appears somewhere...

We suspected that maybe some way though the PRAC algorithm the residues (mod p) "go zero", i.e. we get the point at infinity on the curve, and get stuck there. That would explain why supplying the prime 373 via -go does not find the factor - the -go code uses a simple binary additon ladder, not PRAC.

Paul Zimmermann was able to confirm this suspicion:

Originally Posted by Paul Zimmermann

I've investigated further and I guess that you are both correct :-)
Indeed as conjectured by Alex the "prac" algorithm goes through the
computation of 23P. More precisely to compute 373P it computes at some
point A=63P B=29P C=|A-B|=34P. The next step is to replace B by A+B,
which gives B=92P. But since 92=4*23, we get B=(5461051122294227 : 0),
thus B is the point at infinity. The next step computes 155P = 63P + 92P
knowing the difference 29P, and this is still correct since the "add3" function
works if one of (x1:z1) or (x2:z2) is the point at infinity. The problem comes
from the next step, where we compute 155P + 63P knowing the difference 92P.
More precisely 155P is represented by (352101332154742 : 1209249988666152)
[with -mpzmod to avoid Montgomery representation which complicates things]
and 63P by (15889330945101281 : 12525994685524041). You can check that both
ratios x/z mod p=33554520197234177 are the same, so David was right too.

Here it is the *difference* (x:z) that is the point at infinity in add3,
and in that case add3 returns (0:0). Thus a value of z=0 that appears during
the prac computation will survive until the end.

In summary:
(a) the add3 code is incorrect. When z=0 it should call duplicate() instead
(but this would need to pass the 'b' parameter to add3 too...)
(b) we should not change anything, since this solving this 'bug' should
reduce the number of factors found...

Paul

What is interesting about this is that it is a genuine bug we found - the PRAC algorithm as currently implemented in GMP-ECM (and possibly in Prime95) is incorrect. We are using a function to add distinct points when they are identical, and the function to double the point would have to be used. But so far as we can tell, the only effect of this bug is that it (very rarely) helps find factors that would otherwise be missed - a genuine bug that genuinely makes the program better!

Alex