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

>

>My post:

>

>http://www.mersenneforum.org/showpost.php?p=38252&postcount=8

>

>or the entire thread:

>

>http://www.mersenneforum.org/showthread.php?t=2783

>

>-Jason

>

>

>(Please be kind! I'm not really a mathematician! ;-)

>

>

>

>

>

>Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.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.

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

and,

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.