Lucas-Lehmer Sequence

I'm running several copies of Prime95, the Win32 client software for George Woltman's Great Internet Mersenne Prime Search. Are you? It's free, works in the background, and has a monetary incentive should your computer be the first one to actually prove that a given Mersenne number is prime.

George does a good job of explaining how the Lucas-Lehmer sequence is used to prove primality of a Mersenne number (number in the form of 2^p - 1). But, I wasn't satisfied just knowing that if you iterate through a sequence modulo a Mersenne number, that you'll eventually get zero (after p-2 iterations) if the number is prime. So, I did my own investigating trying to see if there was a way to shortcut the sequence, that is, to see if we could start the sequence somewhere other than the beginning.

My investigation is documented in a post at mersenneforum.org, but I'll summarize here.

Basically, after playing with the LL sequence and different starting terms, I discovered that in order to get a zero term (the result for primality), that the term before the zero term (p-3 term) had to be +/- 2^((P+1)/2). This might be a trivial observation, but I couldn't find reference to it.

I also experimented and concluded due to lack of contradiction that composite Mersenne numbers will never have a zero term, regardless of the starting term, with the exception of a starting term of +/- 2^((P+1)/2).

So, a way to shortcut the LL sequence is to prove that the p-3 iteration is +/- 2^((P+1)/2).

Why must the p-3 term be that? That's simple to show:

(2^((P+1)/2) ^ 2) - 2 = 2^(P+1) -2= 2*(2^P - 1)= 2*Mp= 0 (mod Mp)

So, if the LL sequence must have this special term in order for Mp to be prime, then all we need to do is try to prove that there will be a natural p-4 term that will produce the value of this p-3 term....

In other words:

T^2 = 2^((p+1)/2) + x*Mp + 2 [T is the p-4 term]

or

T^2 = 2^((p+1)/2) + 2 (mod Mp)

This is the same thing as proving that 2^((p+1)/2) + 2 is a quadratic residue modulo Mp.

Unfortunately, this is where I stopped my efforts, because proving that a number is a QR is just about as difficult as iterating the entire LL sequence.

I'll pick this up again later.