mersenneforum.org  

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

Reply
 
Thread Tools
Old 2009-09-29, 11:14   #1
kurtulmehtap
 
Sep 2009

22·32 Posts
Default proof the lucas lehmer test

Dear All,
The last iteration of The Lucas Lehmer requires:
(Sn^2 - 2)mod(2^n - 1) =0
In other form :
Sn^2 = k (2^n - 1)

I wonder if there is only one pair of Sn and k for the given n.
If there is only one k and Sn can someone provide a formal proof?
Sorry, I am an engineer not a math guy.
kurtulmehtap is offline   Reply With Quote
Old 2009-09-29, 12:22   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

11101001001002 Posts
Default

Quote:
Originally Posted by kurtulmehtap View Post
Dear All,
The last iteration of The Lucas Lehmer requires:
(Sn^2 - 2)mod(2^n - 1) =0 [sic]
In other form :
Sn^2 = k (2^n - 1) [sic]; this is wrong.

I wonder if there is only one pair of Sn and k for the given n.
If there is only one k and Sn can someone provide a formal proof?
Sorry, I am an engineer not a math guy.
Sorry, but I can't make sense of your question. The value of k
is irrelevant. And I don't know what you might mean about a
different possible S_n. One has no control over the value of S_n.
It's value is determined recursively from the initial seed and the
value of 2^n-1.

And your specification for the actual test is wrong as well.

Are you asking about a different initial seed? The answer to that
question is yes. Other seed values than 4 can be used. But changing
the seed is irrelevant to either the speed of the test or determining
if 2^n-1 is prime.

What are youREALLY asking?
R.D. Silverman is offline   Reply With Quote
Old 2009-09-29, 12:23   #3
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

1,117 Posts
Default

I believe that what you mean to say is that Sn-1=k(2n-1), where the sequence Sm is defined as S1=4 and Sm=(Sm-1)2-2 for m>1. If 2n-1 is prime, we do not get Sm a multiple of 2n-1 until the (n-1)-st step, is that what you are asking? You could take a look at the proof on the Mersennewiki: http://www.mersennewiki.org/index.php/Lucas-Lehmer_Test
philmoore is offline   Reply With Quote
Old 2009-09-29, 12:35   #4
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

10AB16 Posts
Default

I'm pretty sure he's asking (translated to modular arithmetic terms) if a step in the LL test will result in a 0, and then if you were to continue the LL sequence, if it would result in a 0 again. Or, as he put it, if there is ever more than one Sn and k pair for a given p such that Sn = k(2^p-1).
Here is the answer to that: There is only one such Sn and k pair for any given LL sequence, which is clear from looking at the next few lines if you were to continue after you reach 0 mod 2^p-1.

Sm = 0 mod 2^n-1
residue is 0 (if n is prime and m=n-2, then you've just completed the LL test and 2^n-1 is prime)

S(m+1) = (0^2 - 2) mod 2^n-1 = -2 mod 2^n-1
residue is -2

S(m+2) = ((-2)^2 - 2) mod 2^n-1 = 2 mod 2^n-1
residue is 2

S(m+3) = (2^2 - 2) mod 2^n-1 = 2 mod 2^n-1
residue is 2

S(m+4) = (2^2 - 2) mod 2^n-1 = 2 mod 2^n-1
residue is 2
...
Since it continues as 2 infinitely once you reach 0, you can never reach 0 again. (and in case you're curious, like me, the result is the same whether you consider the -2 residue to simply be -2 or to be (2^p-1)-2=2^p-3)

Last fiddled with by Mini-Geek on 2009-09-29 at 12:45
Mini-Geek is offline   Reply With Quote
Old 2009-09-29, 12:46   #5
kurtulmehtap
 
Sep 2009

22×32 Posts
Default

Here is an example to explain my stupid question:
Take the last iteration of the Lucas lehmer Test for 127
((111)^2 -2) mod 127 = 0
In other words
(111)^2 - 2= 97*127 Here Sn =111 and k=97.

However there's also
(16)^2 -2 = 2*127 here Sn=16 and k=2

I know that 111 is the correct residual and 16 is the wrong one.

I was asking if there are other combinations of Sn and k (16-2 and 111-97 for 127) for a given n. And is there a formal proof

Quote:
Originally Posted by R.D. Silverman View Post
Sorry, but I can't make sense of your question. The value of k
is irrelevant. And I don't know what you might mean about a
different possible S_n. One has no control over the value of S_n.
It's value is determined recursively from the initial seed and the
value of 2^n-1.

And your specification for the actual test is wrong as well.

Are you asking about a different initial seed? The answer to that
question is yes. Other seed values than 4 can be used. But changing
the seed is irrelevant to either the speed of the test or determining
if 2^n-1 is prime.

What are youREALLY asking?
kurtulmehtap is offline   Reply With Quote
Old 2009-09-29, 12:53   #6
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by kurtulmehtap View Post
Here is an example to explain my stupid question:
Take the last iteration of the Lucas lehmer Test for 127
((111)^2 -2) mod 127 = 0
In other words
(111)^2 - 2= 97*127 Here Sn =111 and k=97.

However there's also
(16)^2 -2 = 2*127 here Sn=16 and k=2

I know that 111 is the correct residual and 16 is the wrong one.

I was asking if there are other combinations of Sn and k (16-2 and 111-97 for 127) for a given n. And is there a formal proof
Your entire question is wrong headed. It isn't that "16 is the wrong one".
There are infinitely many integers x such that x^2-2 = 0 mod 2^n-1.

You don't get to SELECT S_{n-1] as an input to the test.

S_k is determined RECURSIVELY from S_{k-1}; with S_0 = 4.

And the value of k (as you use it) is totally irrelevant.
R.D. Silverman is offline   Reply With Quote
Old 2009-09-29, 14:05   #7
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

293110 Posts
Default

The value of your k gets so large so fast its hard to comprehend. For a 45,000,000 test where the "frontwave" of LL-testing is atm, your k is around 1010[sup]13,500,000[/sup]. That means the number of digits in k, is itself a number with 13,500,000 digits.

I found out (not proven though) that when 2p-1 is prime, your k is 2*(c*2p-1) where c is another enormous odd number. So that the final step which you call Sn, which is actually called Sn-2 if you start with S0=4 is:
Sp-2 = (2p-1)*2*(c*2p-1)

but only when 2p-1 is prime, and if you start with S0=4.

Last fiddled with by ATH on 2009-09-29 at 14:09
ATH is online now   Reply With Quote
Old 2009-09-29, 15:23   #8
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17×251 Posts
Default

Quote:
Originally Posted by ATH View Post
The value of your k gets so large so fast its hard to comprehend. For a 45,000,000 test where the "frontwave" of LL-testing is atm, your k is around 1010[sup]13,500,000[/sup]. That means the number of digits in k, is itself a number with 13,500,000 digits.

I found out (not proven though) that when 2p-1 is prime, your k is 2*(c*2p-1) where c is another enormous odd number. So that the final step which you call Sn, which is actually called Sn-2 if you start with S0=4 is:
Sp-2 = (2p-1)*2*(c*2p-1)

but only when 2p-1 is prime, and if you start with S0=4.
M127's penultimate LL step is 2^64.
(2^64)^2-2=2^128-2
2^128-2=2*M127=k
So if k=c*2^p-1, then
2*(2^127-1)=c*2^127-1
2^128-2=c*2^127-1
2^128-1=c*2^127
But M127 doesn't divide M128, so c isn't an integer. Perhaps it was supposed to be k=c*(2^p-1)? Trying that...
2*(2^127-1)=c*(2^127-1)
2=c
But c is supposed to be odd, and enormous. There's definitely something wrong here.
Maybe you meant in the case that you don't reduce modulo Mp each iteration. Let's try that with M7=2^7-1=127. With S0=4 and S(n+1)=Sn^2-2, S5 is 2005956546822746114. 2005956546822746114=2*127*7897466719774591. Bingo, that's it! I wouldn't imagine a proof of that would be terribly difficult, assuming it always holds true...
Mini-Geek is offline   Reply With Quote
Old 2009-09-30, 00:55   #9
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

3·977 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
M127's penultimate LL step is 2^64.
(2^64)^2-2=2^128-2
2^128-2=2*M127=k
So if k=c*2^p-1, then
2*(2^127-1)=c*2^127-1
2^128-2=c*2^127-1
2^128-1=c*2^127
But M127 doesn't divide M128, so c isn't an integer. Perhaps it was supposed to be k=c*(2^p-1)? Trying that...
2*(2^127-1)=c*(2^127-1)
2=c
But c is supposed to be odd, and enormous. There's definitely something wrong here.
Maybe you meant in the case that you don't reduce modulo Mp each iteration. Let's try that with M7=2^7-1=127. With S0=4 and S(n+1)=Sn^2-2, S5 is 2005956546822746114. 2005956546822746114=2*127*7897466719774591. Bingo, that's it! I wouldn't imagine a proof of that would be terribly difficult, assuming it always holds true...
That's right I meant without the modulo step, like the OP also meant. I tested my "theory" 2.5 years ago up to 231-1 directly and up to M28 = 286,243 - 1 by doing mod (2*Mp*2p) and mod (4*Mp*2p):
http://www.mersenneforum.org/showpos...5&postcount=21
http://www.mersenneforum.org/showpos...5&postcount=33
http://www.mersenneforum.org/showpos...5&postcount=34
ATH is online now   Reply With Quote
Old 2009-10-01, 12:56   #10
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by ATH View Post
That's right I meant without the modulo step, like the OP also meant. I tested my "theory" 2.5 years ago up to 231-1 directly and up to M28 = 286,243 - 1 by doing mod (2*Mp*2p) and mod (4*Mp*2p):
http://www.mersenneforum.org/showpos...5&postcount=21
http://www.mersenneforum.org/showpos...5&postcount=33
http://www.mersenneforum.org/showpos...5&postcount=34
So let's get back to the original question. What was the O.P. really
looking for???
R.D. Silverman is offline   Reply With Quote
Old 2009-10-01, 20:43   #11
m_f_h
 
m_f_h's Avatar
 
Feb 2007

24×33 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
So let's get back to the original question. What was the O.P. really
looking for???
To oversimplify a bit: I think he essentially wanted to know whether there are 2 different x such that x^2-2 = 0 (in Z/qZ).

Of course, if x is a solution, then -x is a solution too; e.g. 16 = -111 in Z_127.

Last fiddled with by m_f_h on 2009-10-01 at 20:45
m_f_h 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
A second proof for the Lucas-Lehmer Test carpetpool Miscellaneous Math 2 2017-07-30 09:21
Lucas-Lehmer test proof etc. science_man_88 Miscellaneous Math 48 2010-07-14 23:33
Lucas-Lehmer Test storm5510 Math 22 2009-09-24 22:32
Lucas-Lehmer Test proof alpertron mersennewiki 16 2006-03-18 07:23

All times are UTC. The time now is 12:09.

Sun Sep 20 12:09:59 UTC 2020 up 10 days, 9:20, 0 users, load averages: 2.44, 2.28, 1.94

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