20050831, 22:41  #1 
"Nancy"
Aug 2002
Alexandria
2^{5}·7·11 Posts 
ECM puzzle (hard)
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 GMPECM 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 
20050908, 19:08  #2  
"Nancy"
Aug 2002
Alexandria
2464_{10} Posts 
I admit that this puzzle was a bit unfair, but I think the answer is interesting enough to post it anyways.
GMPECM (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 (ab)*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:
Alex Last fiddled with by akruppa on 20050910 at 16:09 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Hard Drive Failure? In 3... 2... 1...  TheMawn  Lounge  32  20131012 06:06 
Hard reboot  dans  Hardware  5  20091230 08:22 
Any puzzle I can't solve in 15 minutes is to be considered HARD  JuanTutors  Puzzles  14  20050527 21:27 
Learning About RAM the Hard Way  Longshot  Hardware  5  20050521 16:40 
wow...1 Tb hard drive  ixfd64  Hardware  8  20040603 20:37 