Thread: LL test speed up? View Single Post 2004-08-18, 15:45   #8
jfollas

Jul 2004

1410 Posts Quote:
 Originally Posted by ppo one interesting thing is that if we do like I suggested in my previous post, S(n-3) seems to be always equal to 2^((n+1)/2), when M is prime. ( I have only tested with some small values of n). Someone has a proof for that ?
Well, that's an important discovery that I made earlier this year and have been developing ever since.... I call this "Shortcutting the Lucas-Lehmer Test" because all you need to do is prove that the S(p-3) term is equal to +/- 2^((p+1)/2).

I was preparing a paper on the subject, but I'll provide some details of my research here (since the cat's already out of the bag )...

In my paper, I set up 3 Lemmas:

LEMMA 1: Mersenne Primes are the only number whose Lucas-Lehmer modulo sequence will result in a term of "zero" after some arbitrary number of iterations.

LEMMA 2: Using a starting value other than "4" for the Lucas-Lehmer sequence modulo 2^p - 1 *may* result in a term of "zero" at some iteration prior to p-2 for Mersenne Prime 2^p - 1. However, a different starting term may also result in no "zero" term after any number of iterations.

LEMMA 3: For any Mersenne Prime Mp, the Lucas-Lehmer sequence modulo that prime will have a term of +/- 2^((P+1)/2) just prior to the term of "zero".

Lemma 1 was a conclusion that I came to based on a lack of contradiction.

Lemma 2 comes from the simple notion that if you start with any actual intermediate term of a LL sequence modulo a Mersenne prime, then you will still get zero, only it will be less than p-2 iterations. But not all numbers < Mp are actual intermediate terms.

When combined, Lemmas 1 and 2 imply that regardless of the starting term, if a LL sequence modulo a Mersenne number yields a "zero" term after some number of iterations > 1, then that Mersenne number is prime. (proof?)

Acceptable starting terms that will produce "zero" terms on the p-2'th iteration for Mersenne prime Mp are found in Sloane's A018844:

A=4, A=52, An=(14*A[n-1]) - A[n-2] (mod Mp)

To date, I have not found a contradiction to my Lemma 1 for Mersenne composites using any starting term (with the exception noted below).

So, why does Lemma 3 (the p-3 term) work? Well, simply put, it satisfies the LL Primality test because if you square it, and then subtract 2, you left with 0 (mod Mp), which is the expected result for the p-2 term modulo prime Mp.

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

Note also that it's not sufficient to just start the LL sequence with 2^((P+1)/2) because it will produce a zero term after only one iteration for all values of P.

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. (I'm going to refer to 2^((p+1)/2) + 2 as "Cp" for the rest of this post....)

Proving that a number is a quadratic residue involves calculating the Legendre Symbol (which will be +1 if it is a QR, -1 if it is not a QR, and undefined for non-prime Mp's. In this case, undefined means not +/- 1).

The Legendre symbol [C\M] is calculated as:

C^((M-1)/2)

Example: [130\8191] = 130^4095 (= +1, meaning that 130 is a QR of 8191)

What I've spent most of my time on over the last several months is trying to optimize the proving/disproving of whether the "Cp" is a quadratic residue of Mp.

One method that I came up with is similar to the LL test in that it involves repeated squaring, and then checking the results. It's similar to LL in that you square the proceeding term, but different because you don't need to subtract 2 with each iteration.

Using the 130\8191 example above, and without going into too much background, it is easy to see that 130^4096 would have to be equal to "130" if 130 is a QR of 8191. Since 4096 is a power of 2, this means that we would only have to repeatedly modular square 130 a total of 12 times, and then see if the result is equal to "130". If so, then we proved Mp to be prime, else it is composite.

I was working on another method that didn't turn out to be very efficient, but it needed to calculate the modular (multiplicative) inverse of "Cp". This is actually very trivial, because the resulting number in binary will have "p" bits with the high order bits set to 1 and the low order bits set to 0 (with the division being half way, giving the larger half to the 1's). I know I didn't describe that well, so here's the example:

8191 = 2^13 - 1 (P=13)

130^-1 (mod 8191) = 1111111000000 (7 1's and 6 0's)
=8128

This is also 8192 - 64. So, as a generalization, the modular inverse of "Cp" term is 2^p - 2^((p-1)/2).

Ok, so if Mp is prime, then the modular inverse will actually be the same as Cp^(((Mp-1)/2)-1). Or, in the 8191 example, this is 130^4094. Proving this fact is where I started to go, but I abandoned this idea because I could not find an improvement in efficiency.

It is important to note that even Mersenne composites will have the same format of modular inverse of Cp. But, the cyclical period is shorter (based on the factors of Mp), so Cp^((2^(p-1))-2) will not be equal to the modular inverse of Cp.

Hopefully this research will spark new ideas for efficient ways to shortcut the LL sequence. It's been pretty fun for me working on it alone, but I welcome others to improve on my work.  