Re: [PrimeNumbers] Shortcutting the Lucas-Lehmer Test
- jfollas wrote:
>I've been researching a concept involving shortcutting the Lucas-Speaking of speeding up LL - I noticed some slightly odd behaviour a
>Lehmer primality test for Mersenne numbers over the past several
>months. Today, prompted by someone posting on mersenneforums the
>same critical discovery that I made, I have released a summarization
>of my off-and-on research effort. I welcome the members of this
>group to review my findings.
>or the entire thread:
>(Please be kind! I'm not really a mathematician! ;-)
>Unsubscribe by an email to: email@example.com
>The Prime Pages : http://www.primepages.org/
>Yahoo! Groups Links
while ago in the course of writing some (very) simple little java
programs for finding Mp's - I'd be interested if anyone investigated
further/ even confirmed my findings...?
What I found (apparently) was that [and I only tested relatively small
indices of Mn's - up to a couple of thousand or so] a 3-PRP test (or
maybe even a 3-Wanless test, with the extra level of exponentiation for
even greater accuracy - see my earlier post for details of "wanless
test") was actually somewhat quicker than a LL test.
This surprised me somewhat (I have to say), but at the time I put it
down (presumably) to java's efficient implementation of the "Russian
Peasant" method of modular exponentiation.
- If we look at the known test:
A Mersenne number M(p) is prime if M(p) divides S(p-2) where S(0)=4
S(p)=S(p-1)^2 -2(mod 2^p -1)
My double case test/probable test: (where L(n) are Lucas numbers, via
the golden proportion)(10/19/01) The golden ratio could speed up the
squarings involved. Since there are various algorithmic ways to
generate Lucas numbers, by adding fractals etc. The mod here, would
be subracted at each add, rather than divided out.
L(2^(p-1))mod 2^p -1 = 0 [CASE1]
L(2^(p-1) -1) mod 2^p -1 = 0 [CASE2]
Or L(2^(p-1) -1)mod 2^p +1 /3 = 0[CASE2]
2^2-1=3 divides L(2)=3 [C1]
2^3-1=7 divides, L(4)=7 [C1]
2^5-1=31 divides, L(15)=1364 [C2]
2^7-1=127 divides, L(64)=23725150497407 [C1]
2^13-1=8191 divides, L(4095) [C2]
2^17-1=131071 divides, L(65535) [C2]
2^19-1=524287 divides, L(262144) [C1]
So, also with F(n): (Fibonacci numbers)
F(2^p) mod 2^p -1 = 0[Case 1]
F(2^p -2) mod 2^p -1 = 0[Case 2]
F(2^p -2) mod 2^p +1 /3 = 0[Case 2]
2^2-1=3 divides F(4)=3 [C1]
2^3-1= 7 divides F(8)=21 [C1]
2^5-1=31 divides F(30)=832040, [C2]
2^7-1=127 divides F(128)=251728825683549488150424261 [C1]
2^13-1=8191 divides F(8190) [C2]
2^17-1=131071 divides F(131070) [C2]
2^19-1=524287 divides F(524288) [C1]
David Broadhurst wrote me:
The classic Lucas-Lehmer test for Mersennes
uses the Lucas sequence with
p=2, q=-2, d=p^2-4*q=12 (Ribenboim p.92).
You can "probably" use the same batch of theorems
from Ribenboim to prove the necessity and sufficiency
of your more complicated two-case test with
p=1, q=-1, d=p^2-q=5 (i.e. the rabbit case).
This is proven completey true up to Lucas# = L(2^4499)
Though, the residue of the Mersenne exponent mod 4, decides whether
or not the test is deterministic.