20171113, 16:22  #1 
Nov 2016
23 Posts 
Testing Mersenne Primes with Elliptic Curves
In reference to the paper by Song Y. Yan and Glyn James:
https://books.google.co.uk/books?id=...913089&f=false I've clipped example 3 below, as well as the explanation of the algorithm. How do we get the series of numbers 2060, 4647, 6472, 3036,362,0 from that algorithm? 
20171113, 17:26  #2 
Aug 2006
5,923 Posts 
I get the same thing. Where do you get stuck?
For the first step, you have G = 2 and are computing (G^2+12)^2/(4*G*(G^212)) mod 2^131 (4+12)^2/(4*2*(412)) mod 2^131 16^2/(4*2*8) mod 2^131 4 mod 2^131 For the second step, you have G = 4 and are computing (G^2+12)^2/(4*G*(G^212)) mod 2^131 (4^2+12)^2/(4*4*(4^212)) mod 2^131 (16+12)^2/(4*4*4) mod 2^131 28^2/64 mod 2^131 49/4 mod 2^131 49*2048 mod 2^131 2060 mod 2^131 I'm guessing the troublesome step was finding 1/4 mod 2^131, yes? I think the usual way is the extended Euclidean algorithm. The special case of powers of two mod Mersenne numbers is easier. Here's the code I used to check the sequence your book gave: Code:
isMersenneComposite(p)= { if(!isprime(p), error("Must be prime")); my(Mp=2^p1,G=Mod(2,Mp),G2); for(i=1,p2, G2=G^2; G=(G2+12)^2/(4*G*(G212)); print(lift(G)); if(gcd(lift(G),Mp)>1,return(gcd(lift(G),Mp))); \\ return the factor if(gcd(lift(G212),Mp)>1,return(gcd(lift(G212),Mp))) \\ return the factor ); G2=G^2; G=(G2+12)^2/(4*G*(G212)); print(lift(G)); gcd(lift(G),Mp)==1; \\ return 1 if composite but no factor found, or 0 if prime } addhelp(isMersenneComposite, "isMersenneComposite(p): Checks if 2^p1 is a composite number, given some prime p. If so, return either 1 or some factor of the number. If not (2^p1 is prime) return 0."); > isMersenneComposite(13) 4 2060 4647 6472 5719 1060 6616 6568 2703 3036 362 0 %1 = 0 
20171115, 19:11  #3 
Nov 2016
23 Posts 
Thank you for your reply CRGreathouse  I tried out the code and it works well.
I'm still stuck on how to get from: 49/4 mod 2^131 to 49*2048 mod 2^131 I'd be grateful if you could elaborate. [Edit] Sorry, got it. ModularInverse[4,8191] = 2048 Last fiddled with by a nicol on 20171115 at 19:22 
20171115, 20:23  #4 
Aug 2006
1723_{16} Posts 
Exactly. Can you do it with 17 now?

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Distribution of Mersenne primes before and after couples of primes found  emily  Math  34  20170716 18:44 
Need help with elliptic curves...  WraithX  Math  12  20100929 09:34 
New coordinate system for elliptic curves  wpolly  GMPECM  5  20070718 13:18 
Elliptic curves in NFS  otkachalka  Factoring  5  20051120 12:22 
Mersenne Wiki: Improving the mersenne primes web site by FOSS methods  optim  PrimeNet  13  20040709 13:51 