In mathematics, the Lucas–Lehmer–Riesel test is a primality test for numbers of the form N = k · 2n − 1 with odd k < 2n. 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 (see Pocklington primality test) are used.
The algorithm 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:
u i = u i − 1 2 − 2. {\displaystyle u_{i}=u_{i-1}^{2}-2.}
Then N = k · 2n − 1, with k < 2n, is prime if and only if it divides un−2.
Finding the starting value The starting value u0 is determined as follows.
If k ≡ 1 or 5 (mod 6): if 1 (mod 6) and n is even, or 5 (mod 6) and n is odd, then 3 divides N, and there is no need to test. Otherwise, N ≡ 7 (mod 24) and the Lucas sequence V(4,1) may be used: we take u 0 = ( 2 + 3 ) k + ( 2 − 3 ) k {\displaystyle u_{0}=(2+{\sqrt {3}})^{k}+(2-{\sqrt {3}})^{k}} , which is the kth term of that sequence. This is a generalization of the ordinary Lucas–Lehmer test, and reduces to it when k = 1. Otherwise, we are in the case where k is a multiple of 3, and it is more difficult to select the right value of u0. It is known that if k = 3 and n ≡ 0 or 3 (mod 4), then we can take u0 = 5778. 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:
( P − 2 N ) = 1 and ( P + 2 N ) = − 1. {\displaystyle \left({\frac {P-2}{N}}\right)=1\quad {\text{and}}\quad \left({\frac {P+2}{N}}\right)=-1.}
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 Rödseth 1994 as well as page 124 of Riesel 1994. The latter explains that when 3 ∤ k, P = 4 may be used as above, and no further search is necessary. The starting value u0 will be the Lucas sequence term Vk(P,1) taken modulo N. This process of selection takes very little time compared to the main test.
How the test works 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, then 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. We start off by trying to find a non-iterative expression for the ui. Following the model of the Lucas–Lehmer test, put ui = a2i + a−2i, and by induction we have ui = u2i−1 − 2. So we can consider ourselves as looking at the 2ith term of the sequence v(i) = ai + ai. If a satisfies a quadratic equation, then this is a Lucas sequence, and has an expression of the form v(i) = α v(i−1) + β v(i−2). Really, we are looking at the k · 2ith term of a different sequence, but since decimations (take every kth term starting with the zeroth) of a Lucas sequence are themselves Lucas sequences, we can deal with the factor k by picking a different starting point.
… excerpt ends here. Continue reading the full article.
