Thread: ECM puzzle (hard) View Single Post
2005-09-08, 19:08   #2
akruppa

"Nancy"
Aug 2002
Alexandria

246410 Posts

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:

Quote:
 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

Last fiddled with by akruppa on 2005-09-10 at 16:09