Testing Mersenne Primes with Elliptic Curves

[a nicol]

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?

[CRGreathouse]

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:

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

[a nicol]

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

[CRGreathouse]

Exactly. Can you do it with 17 now?