mersenneforum.org  

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

Reply
 
Thread Tools
Old 2012-05-09, 22:56   #1
MrRepunit
 
MrRepunit's Avatar
 
Mar 2011
Germany

97 Posts
Default 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)}
MrRepunit is offline   Reply With Quote
Old 2012-05-09, 23:02   #2
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3·29·83 Posts
Default

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.
Dubslow is offline   Reply With Quote
Old 2012-05-09, 23:08   #3
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

9A316 Posts
Default

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.
akruppa is offline   Reply With Quote
Old 2012-05-09, 23:13   #4
MrRepunit
 
MrRepunit's Avatar
 
Mar 2011
Germany

11000012 Posts
Default

Quote:
Originally Posted by akruppa View Post
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
MrRepunit is offline   Reply With Quote
Old 2012-05-09, 23:38   #5
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by MrRepunit View Post
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
science_man_88 is offline   Reply With Quote
Old 2012-05-10, 00:01   #6
MrRepunit
 
MrRepunit's Avatar
 
Mar 2011
Germany

11000012 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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).
MrRepunit is offline   Reply With Quote
Old 2012-05-10, 00:07   #7
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by MrRepunit View Post
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
science_man_88 is offline   Reply With Quote
Old 2012-05-10, 00:15   #8
MrRepunit
 
MrRepunit's Avatar
 
Mar 2011
Germany

97 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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
MrRepunit is offline   Reply With Quote
Old 2012-05-10, 00:27   #9
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by MrRepunit View Post
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.
science_man_88 is offline   Reply With Quote
Old 2012-05-10, 03:50   #10
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

35·41 Posts
Default

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
LaurV is offline   Reply With Quote
Reply

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

All times are UTC. The time now is 17:55.


Thu May 26 17:55:20 UTC 2022 up 42 days, 15:56, 2 users, load averages: 1.99, 1.71, 1.71

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔