Thread: LL test speed up? View Single Post
2005-09-20, 01:10   #11

"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·599 Posts

Quote:
 Originally Posted by jfollas 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).
... and all you need to do to calculate S(p-3) is to calculate S(1), S(2), S(3), ... and so on up to S(p-3) --- which is exactly what the Lucas-Lehmer test already does. So there's no shortcut!! For all but the smallest p (< a few hundred), you can't tell whether S(p-3) = +/- 2^((p+1)/2) mod 2^p-1 unless you perform all the previous S(i) calculations.

Quote:
 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....
But that's not useful in speeding up the testing unless you come up with a way of calculating S(p-4) mod 2^p-1 that's faster than the L-L sequence, is it?

Quote:
 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.
So it's computationally equivalent to L-L, not a speedup (the subtraction of 2 is trivial).