mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2017-11-13, 16:22   #1
a nicol
 
Nov 2016

23 Posts
Default 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
Click image for larger version

Name:	algorithm2-elliptic.PNG
Views:	97
Size:	65.9 KB
ID:	17194   Click image for larger version

Name:	elliptic-example-3.PNG
Views:	87
Size:	86.3 KB
ID:	17195  
a nicol is offline   Reply With Quote
Old 2017-11-13, 17:26   #2
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2×3×977 Posts
Default

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
CRGreathouse is offline   Reply With Quote
Old 2017-11-15, 19:11   #3
a nicol
 
Nov 2016

23 Posts
Default

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.

[Edit]
Sorry, got it.
ModularInverse[4,8191] = 2048

Last fiddled with by a nicol on 2017-11-15 at 19:22
a nicol is offline   Reply With Quote
Old 2017-11-15, 20:23   #4
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2×3×977 Posts
Default

Exactly. Can you do it with 17 now?
CRGreathouse is offline   Reply With Quote
Reply

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 2017-07-16 18:44
Need help with elliptic curves... WraithX Math 12 2010-09-29 09:34
New coordinate system for elliptic curves wpolly GMP-ECM 5 2007-07-18 13:18
Elliptic curves in NFS otkachalka Factoring 5 2005-11-20 12:22
Mersenne Wiki: Improving the mersenne primes web site by FOSS methods optim PrimeNet 13 2004-07-09 13:51

All times are UTC. The time now is 05:32.

Wed Jul 15 05:32:52 UTC 2020 up 112 days, 3:05, 0 users, load averages: 1.72, 1.53, 1.48

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.