mersenneforum.org > Math Testing Mersenne Primes with Elliptic Curves
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2017-11-13, 16:22 #1 a nicol   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? Attached Thumbnails
 2017-11-13, 17:26 #2 CRGreathouse     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^2-12)) mod 2^13-1 (4+12)^2/(4*-2*(4-12)) mod 2^13-1 16^2/(4*2*8) mod 2^13-1 4 mod 2^13-1 For the second step, you have G = 4 and are computing (G^2+12)^2/(4*G*(G^2-12)) mod 2^13-1 (4^2+12)^2/(4*4*(4^2-12)) mod 2^13-1 (16+12)^2/(4*4*4) mod 2^13-1 28^2/64 mod 2^13-1 49/4 mod 2^13-1 49*2048 mod 2^13-1 2060 mod 2^13-1 I'm guessing the troublesome step was finding 1/4 mod 2^13-1, 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^p-1,G=Mod(-2,Mp),G2); for(i=1,p-2, G2=G^2; G=(G2+12)^2/(4*G*(G2-12)); print(lift(G)); if(gcd(lift(G),Mp)>1,return(gcd(lift(G),Mp))); \\ return the factor if(gcd(lift(G2-12),Mp)>1,return(gcd(lift(G2-12),Mp))) \\ return the factor ); G2=G^2; G=(G2+12)^2/(4*G*(G2-12)); 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^p-1 is a composite number, given some prime p. If so, return either 1 or some factor of the number. If not (2^p-1 is prime) return 0."); > isMersenneComposite(13) 4 2060 4647 6472 5719 1060 6616 6568 2703 3036 362 0 %1 = 0
 2017-11-15, 19:11 #3 a nicol   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^13-1 to 49*2048 mod 2^13-1 I'd be grateful if you could elaborate.  Sorry, got it. ModularInverse[4,8191] = 2048 Last fiddled with by a nicol on 2017-11-15 at 19:22
 2017-11-15, 20:23 #4 CRGreathouse     Aug 2006 172316 Posts Exactly. Can you do it with 17 now?

 Similar Threads Thread Thread Starter Forum Replies Last Post emily Math 34 2017-07-16 18:44 WraithX Math 12 2010-09-29 09:34 wpolly GMP-ECM 5 2007-07-18 13:18 otkachalka Factoring 5 2005-11-20 12:22 optim PrimeNet 13 2004-07-09 13:51

All times are UTC. The time now is 13:02.

Thu Sep 24 13:02:30 UTC 2020 up 14 days, 10:13, 2 users, load averages: 2.52, 2.06, 1.83