Question on Lucas Lehmer variant (probably a faster prime test)

MrRepunit · 2012-05-09, 22:56

Hi,

a friend of mine suggested two new variants of the Lucas Lehmer scheme. In both cases there is no subtraction of 2, just the squaring.
I tested both variants for smaller primes up to 10000 (no false positives) and all Mersenne primes up to 44497 (all positive tests).

So here is my question:
Can one prove that the following algorithm is a prime test for Mersenne numbers?
If not, maybe it could be used as a probable prime test. It should be faster than the usual Lucas Lehmer test.

Here is the algorithm (with two different initial and final conditions):

Code:

LucasLehmer(p)
{ s = a
M = 2^p - 1
repeat p times : s = s*s mod M
if s = a^2 return PRIME else return COMPOSITE
}
variant 1: a = 3
variant 2: a = 5

Pari GP code:
LL1(p)={m=2^p-1;s=3;for(i=1,p,s=lift(Mod(s,m)^2));print(s==9)}
LL2(p)={m=2^p-1;s=5;for(i=1,p,s=lift(Mod(s,m)^2));print(s==25)}

Dubslow · 2012-05-09, 23:02

I'm not sure it is faster. Subtracting two is an easy thing to do, while this test has two more squares. Removing p-2 minus-2 operations may or may not make up for two extra squares, and even if it does, the gains are barely noticeable at best.

akruppa · 2012-05-09, 23:08

Let N = 2^p-1. You compute 3^(2^p) == 3^(N+1) (mod N). This is essentially just a Fermat test. It may correctly determine primality for all Mersenne numbers, but I'm not aware of a proof. The Lucas-Lehmer does provably determine primality for Mersenne numbers, and the subtraction of 2 each iteration is insignificant for computational cost.

MrRepunit · 2012-05-09, 23:13

Quote:

Originally Posted by akruppa

Let N = 2^p-1. You compute 3^(2^p) == 3^(N+1) (mod N). This is essentially just a Fermat test. It may correctly determine primality for all Mersenne numbers, but I'm not aware of a proof. The Lucas-Lehmer does provably determine primality for Mersenne numbers, and the subtraction of 2 each iteration is insignificant for computational cost.

You are totally right, I should have seen that myself (it is getting late here). So it is not faster.
Thanks for pointing this out.

Edit: I did not see it because in the suggestions there were even more variants: real LL tests with different initial values... (Shame on me)

science_man_88 · 2012-05-09, 23:38

Quote:

Originally Posted by MrRepunit

Hi,

a friend of mine suggested two new variants of the Lucas Lehmer scheme. In both cases there is no subtraction of 2, just the squaring.
I tested both variants for smaller primes up to 10000 (no false positives) and all Mersenne primes up to 44497 (all positive tests).

So here is my question:
Can one prove that the following algorithm is a prime test for Mersenne numbers?
If not, maybe it could be used as a probable prime test. It should be faster than the usual Lucas Lehmer test.

Here is the algorithm (with two different initial and final conditions):

Code:

LucasLehmer(p)
{ s = a
M = 2^p - 1
repeat p times : s = s*s mod M
if s = a^2 return PRIME else return COMPOSITE
}
variant 1: a = 3
variant 2: a = 5

Pari GP code:
LL1(p)={m=2^p-1;s=3;for(i=1,p,s=lift(Mod(s,m)^2));print(s==9)}
LL2(p)={m=2^p-1;s=5;for(i=1,p,s=lift(Mod(s,m)^2));print(s==25)}

one thing I'll note, testing the lucas lehmer code in my code file and this with the print turned into a return I noticed that the a=3 situation seems faster but missed the exponent 3. is it true that $3^{(2^p)} -S_{p-2} \equiv 9 \text { mod } 2^p-1$ because this is a necessity for being true no ?

MrRepunit · 2012-05-10, 00:01

Quote:

Originally Posted by science_man_88

one thing I'll note, testing the lucas lehmer code in my code file and this with the print turned into a return I noticed that the a=3 situation seems faster but missed the exponent 3. is it true that $3^{(2^p)} -S_{p-2} \equiv 9 \text { mod } 2^p-1$ because this is a necessity for being true no ?

Right, I forgot to mention that. But it is trivial: s mod (2^3-1) is smaller than 9 (or 25), so 2^p-1 must be larger than 9 (or 25).

science_man_88 · 2012-05-10, 00:07

Quote:

Originally Posted by MrRepunit

Right, I forgot to mention that. But it is trivial: s mod (2^3-1) is smaller than 9 (or 25), so 2^p-1 must be larger than 9 (or 25).

you know you can take outside of coming up with a formula for them take the modular equation to a number below $S_{p-2}$ down to $3^{(2^p)} \text { mod } S_{p-2}$ in fact.

MrRepunit · 2012-05-10, 00:15

Quote:

Originally Posted by science_man_88

you know you can take outside of coming up with a formula for them you could take the modular equation to a number below $S_{p-2}$ down to $3^{(2^p)} \text { mod } S_{p-2}$ in fact.

Yes, it is just a relict of the above algorithm (which I did not "invent" myself). But don't worry too much, it is just a Fermat test in disguise

science_man_88 · 2012-05-10, 00:27

Quote:

Originally Posted by MrRepunit

Yes, it is just a relict of the above algorithm (which I did not "invent" myself). But don't worry too much, it is just a Fermat test in disguise

okay I just thought it might make it easier to test the idea.

LaurV · 2012-05-10, 03:50

The idea is not new, it was many times discussed before. If you do not start with 3, but with some value dependent of each p, you can prove that this test is equivalent to a LL test, functional and computational. For example you start with $a=2^{\frac{p-1}2}+1$ .

One direction is easy to prove, with Fermat, if $M_p=2^p-1$ is prime, the powering $a^{M_p-1}$ mod M_p ends in 1. Multiplying by $a^2$ you get $a^{M_p+1}=a^2$ and the left side is in fact $a^{2^p}$ , which can be computed by repeatedly squaring. The other direction you can prove by taking back two steps on the LL test, starting from the last. For a prime you have S_p-2=0, so S_p-3=msqrt(2,M_p), where msqrt is the modular square root. Let's note it $\pm\sqrt{2}$ . This value exists always (regardless of the primality of M_p), and it is either $2^{\frac{p+1}2}$ or its negative mod M_p. Going a step back, S_p-4 is $\pm\sqrt{2\pm\sqrt 2}$ (mod M_p). We can extract a 2 from the under square root, because as said already, 2 is always a square (mod M_p). What is left is $a=\frac{S_{p-4}}{\sqrt{\pm 2}}=\sqrt{2^{\frac{p-1}2}+1}$ . As M_p is 3 (mod 4), this can be (tentatively) computed by repeated squaring, when you get $a^{2^p}=a^2$ . When Mp is composite, this value does not exists, and the sqrt (tentative) procedure gives you some garbage (if it should give you an "a", then you found a zero in LL residues string, which is impossible).

As I said, the idea is not new, I "rediscovered" it myself some time ago, and post it to the forum, wondering if it is faster then LL test. As it turned out from discussions, it is not, the only improvement is related to subtracting 2, which is computationally insignificant. Further search turned out that other people had different forms of this idea before, more or less provable being LL equivalent, but at the end all it takes is to see that when Mp is prime there is the big ZERO at some iteration in the LL test, which is unique (the terms after are all +/-2), and when Mp is composite, there is no zero, the residues go in a loop after a while.

2012-05-09, 22:56	#1
MrRepunit Mar 2011 Germany 141₈ Posts	Question on Lucas Lehmer variant (probably a faster prime test) Hi, a friend of mine suggested two new variants of the Lucas Lehmer scheme. In both cases there is no subtraction of 2, just the squaring. I tested both variants for smaller primes up to 10000 (no false positives) and all Mersenne primes up to 44497 (all positive tests). So here is my question: Can one prove that the following algorithm is a prime test for Mersenne numbers? If not, maybe it could be used as a probable prime test. It should be faster than the usual Lucas Lehmer test. Here is the algorithm (with two different initial and final conditions): Code: LucasLehmer(p) { s = a M = 2^p - 1 repeat p times : s = s*s mod M if s = a^2 return PRIME else return COMPOSITE } variant 1: a = 3 variant 2: a = 5 Pari GP code: LL1(p)={m=2^p-1;s=3;for(i=1,p,s=lift(Mod(s,m)^2));print(s==9)} LL2(p)={m=2^p-1;s=5;for(i=1,p,s=lift(Mod(s,m)^2));print(s==25)}

2012-05-10, 03:50	#10
LaurV Romulan Interpreter "name field" Jun 2011 Thailand 2⁴·643 Posts	The idea is not new, it was many times discussed before. If you do not start with 3, but with some value dependent of each p, you can prove that this test is equivalent to a LL test, functional and computational. For example you start with $a=2^{\frac{p-1}2}+1$ . One direction is easy to prove, with Fermat, if $M_p=2^p-1$ is prime, the powering $a^{M_p-1}$ mod M_p ends in 1. Multiplying by $a^2$ you get $a^{M_p+1}=a^2$ and the left side is in fact $a^{2^p}$ , which can be computed by repeatedly squaring. The other direction you can prove by taking back two steps on the LL test, starting from the last. For a prime you have S_p-2=0, so S_p-3=msqrt(2,M_p), where msqrt is the modular square root. Let's note it $\pm\sqrt{2}$ . This value exists always (regardless of the primality of M_p), and it is either $2^{\frac{p+1}2}$ or its negative mod M_p. Going a step back, S_p-4 is $\pm\sqrt{2\pm\sqrt 2}$ (mod M_p). We can extract a 2 from the under square root, because as said already, 2 is always a square (mod M_p). What is left is $a=\frac{S_{p-4}}{\sqrt{\pm 2}}=\sqrt{2^{\frac{p-1}2}+1}$ . As M_p is 3 (mod 4), this can be (tentatively) computed by repeated squaring, when you get $a^{2^p}=a^2$ . When Mp is composite, this value does not exists, and the sqrt (tentative) procedure gives you some garbage (if it should give you an "a", then you found a zero in LL residues string, which is impossible). As I said, the idea is not new, I "rediscovered" it myself some time ago, and post it to the forum, wondering if it is faster then LL test. As it turned out from discussions, it is not, the only improvement is related to subtracting 2, which is computationally insignificant. Further search turned out that other people had different forms of this idea before, more or less provable being LL equivalent, but at the end all it takes is to see that when Mp is prime there is the big ZERO at some iteration in the LL test, which is unique (the terms after are all +/-2), and when Mp is composite, there is no zero, the residues go in a loop after a while. Last fiddled with by LaurV on 2012-05-10 at 04:05

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Modifying the Lucas Lehmer Primality Test into a fast test of nothing	Trilo	Miscellaneous Math	25	2018-03-11 23:20
Question About Lucas-Lehmer Test (JAVA)	jmanes92	Programming	9	2013-02-22 22:19
Faster Lucas-Lehmer test using integer arithmetic?	__HRB__	Software	188	2010-08-09 11:13
Lucas Lehmer test question?	BMgf	Programming	23	2003-12-09 08:52
about Lucas-Lehmer test and Prime 95	Annunaki	Math	22	2003-08-05 21:52

2012-05-09, 23:02	#2
Dubslow Basketry That Evening! "Bunslow the Bold" Jun 2011 40<A<43 -89<O<-88 1C35₁₆ Posts	I'm not sure it is faster. Subtracting two is an easy thing to do, while this test has two more squares. Removing p-2 minus-2 operations may or may not make up for two extra squares, and even if it does, the gains are barely noticeable at best.

2012-05-09, 23:08	#3
akruppa "Nancy" Aug 2002 Alexandria 2,467 Posts	Let N = 2^p-1. You compute 3^(2^p) == 3^(N+1) (mod N). This is essentially just a Fermat test. It may correctly determine primality for all Mersenne numbers, but I'm not aware of a proof. The Lucas-Lehmer does provably determine primality for Mersenne numbers, and the subtraction of 2 each iteration is insignificant for computational cost.