Lucas–Lehmer–Riesel test
In mathematics, the Lucas–Lehmer–Riesel test is a primality test for numbers of the form N = k ⋅ 2n − 1, with 2n > k. The test was developed by Hans Riesel and it is based on the Lucas–Lehmer primality test. It is the fastest deterministic algorithm known for numbers of that form. For numbers of the form N = k ⋅ 2n + 1 (Proth numbers), either application of Proth's theorem (a Las Vegas algorithm) or one of the deterministic proofs described in Brillhart-Lehmer-Selfridge 1975 are used.
The algorithm is very similar to the Lucas–Lehmer test, but with a variable starting point depending on the value of k.
Define a sequence {ui} for all i > 0 by:
Then N is prime if and only if it divides un−2.
The starting value u0 is determined as follows.
An alternative method for finding the starting value u0 is given in Rödseth 1994. The selection method is much easier than that used by Riesel for the 3 divides k case. First find a P value that satisfies the following equalities of Jacobi symbols:
In practice, only a few P values need be checked before one is found (5, 8, 9, or 11 work in about 85% of trials).
To find the starting value u0 from the P value we can use a Lucas(P,1) sequence, as shown in as well as page 124 of. The latter explains that when 3 ∤ k, P=4 may be used, hence the earlier search is not necessary. The starting value u0 is then equal to the modular Lucas sequence Vk(P,Q) mod N. This process takes very little time compared to the main test.
The Lucas–Lehmer–Riesel test is a particular case of group-order primality testing; we demonstrate that some number is prime by showing that some group has the order that it would have were that number prime, and we do this by finding an element of that group of precisely the right order.
For Lucas-style tests on a number N, we work in the multiplicative group of a quadratic extension of the integers modulo N; if N is prime, the order of this multiplicative group is N2 − 1, it has a subgroup of order N + 1, and we try to find a generator for that subgroup.
...
Wikipedia