 mersenneforum.org > Math Testing Mersenne Primes with Elliptic Curves
 Register FAQ Search Today's Posts Mark Forums Read 2017-11-13, 16:22 #1 a nicol   Nov 2016 2910 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?   2017-11-13, 17:26 #2 CRGreathouse   Aug 2006 3·1,993 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 29 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 3×1,993 Posts Exactly. Can you do it with 17 now?  Thread Tools Show Printable Version Email this Page 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 20:14.

Fri Jul 1 20:14:22 UTC 2022 up 78 days, 18:15, 0 users, load averages: 2.16, 1.99, 1.99