mersenneforum.org > Math Question on Lucas Lehmer variant (probably a faster prime test)
 Register FAQ Search Today's Posts Mark Forums Read

 2012-05-09, 22:56 #1 MrRepunit     Mar 2011 Germany 6116 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-09, 23:02 #2 Dubslow Basketry That Evening!     "Bunslow the Bold" Jun 2011 40
 2012-05-09, 23:08 #3 akruppa     "Nancy" Aug 2002 Alexandria 46438 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.
2012-05-09, 23:13   #4
MrRepunit

Mar 2011
Germany

97 Posts

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)

Last fiddled with by MrRepunit on 2012-05-09 at 23:21

2012-05-09, 23:38   #5
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

203428 Posts

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 ?

Last fiddled with by science_man_88 on 2012-05-09 at 23:43

2012-05-10, 00:01   #6
MrRepunit

Mar 2011
Germany

97 Posts

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).

2012-05-10, 00:07   #7
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

2·3·23·61 Posts

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.

Last fiddled with by science_man_88 on 2012-05-10 at 00:27

2012-05-10, 00:15   #8
MrRepunit

Mar 2011
Germany

97 Posts

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

2012-05-10, 00:27   #9
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

100000111000102 Posts

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.

 2012-05-10, 03:50 #10 LaurV Romulan Interpreter     "name field" Jun 2011 Thailand 19·541 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 Mp 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 Sp-2=0, so Sp-3=msqrt(2,Mp), where msqrt is the modular square root. Let's note it $\pm\sqrt{2}$. This value exists always (regardless of the primality of Mp), and it is either $2^{\frac{p+1}2}$ or its negative mod Mp. Going a step back, Sp-4 is $\pm\sqrt{2\pm\sqrt 2}$ (mod Mp). We can extract a 2 from the under square root, because as said already, 2 is always a square (mod Mp). What is left is $a=\frac{S_{p-4}}{\sqrt{\pm 2}}=\sqrt{2^{\frac{p-1}2}+1}$. As Mp 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 Trilo Miscellaneous Math 25 2018-03-11 23:20 jmanes92 Programming 9 2013-02-22 22:19 __HRB__ Software 188 2010-08-09 11:13 BMgf Programming 23 2003-12-09 08:52 Annunaki Math 22 2003-08-05 21:52

All times are UTC. The time now is 01:44.

Fri Feb 3 01:44:44 UTC 2023 up 168 days, 23:13, 1 user, load averages: 1.28, 1.25, 1.17