20120509, 22:56  #1 
Mar 2011
Germany
97 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^p1;s=3;for(i=1,p,s=lift(Mod(s,m)^2));print(s==9)} LL2(p)={m=2^p1;s=5;for(i=1,p,s=lift(Mod(s,m)^2));print(s==25)} 
20120509, 23:02  #2 
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 89<O<88
3·29·83 Posts 
I'm not sure it is faster. Subtracting two is an easy thing to do, while this test has two more squares. Removing p2 minus2 operations may or may not make up for two extra squares, and even if it does, the gains are barely noticeable at best.

20120509, 23:08  #3 
"Nancy"
Aug 2002
Alexandria
9A3_{16} Posts 
Let N = 2^p1. 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 LucasLehmer does provably determine primality for Mersenne numbers, and the subtraction of 2 each iteration is insignificant for computational cost.

20120509, 23:13  #4  
Mar 2011
Germany
1100001_{2} Posts 
Quote:
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 20120509 at 23:21 

20120509, 23:38  #5  
"Forget I exist"
Jul 2009
Dartmouth NS
2143_{16} Posts 
Quote:
Last fiddled with by science_man_88 on 20120509 at 23:43 

20120510, 00:01  #6 
Mar 2011
Germany
97 Posts 
Right, I forgot to mention that. But it is trivial: s mod (2^31) is smaller than 9 (or 25), so 2^p1 must be larger than 9 (or 25).

20120510, 00:07  #7 
"Forget I exist"
Jul 2009
Dartmouth NS
5·13·131 Posts 
you know you can take outside of coming up with a formula for them take the modular equation to a number below down to in fact.
Last fiddled with by science_man_88 on 20120510 at 00:27 
20120510, 00:15  #8 
Mar 2011
Germany
97 Posts 
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

20120510, 00:27  #9 
"Forget I exist"
Jul 2009
Dartmouth NS
5×13×131 Posts 

20120510, 03:50  #10 
Romulan Interpreter
"name field"
Jun 2011
Thailand
10100001110110_{2} 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 .
One direction is easy to prove, with Fermat, if is prime, the powering mod M_{p} ends in 1. Multiplying by you get and the left side is in fact , 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_{p2}=0, so S_{p3}=msqrt(2,M_{p}), where msqrt is the modular square root. Let's note it . This value exists always (regardless of the primality of M_{p}), and it is either or its negative mod M_{p}. Going a step back, S_{p4} is (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 . As M_{p} is 3 (mod 4), this can be (tentatively) computed by repeated squaring, when you get . 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 20120510 at 04:05 
Thread Tools  
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  20180311 23:20 
Question About LucasLehmer Test (JAVA)  jmanes92  Programming  9  20130222 22:19 
Faster LucasLehmer test using integer arithmetic?  __HRB__  Software  188  20100809 11:13 
Lucas Lehmer test question?  BMgf  Programming  23  20031209 08:52 
about LucasLehmer test and Prime 95  Annunaki  Math  22  20030805 21:52 