Lucas–Lehmer–Riesel test

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 u_i for all i > 0 by:

${\displaystyle u_{i}=u_{i-1}^{2}-2.\,}$

Then N is prime if and only if it divides u_n−2.

The starting value u₀ is determined as follows.

• If k = 1: if n is odd, then we can take u₀ = 4. If n ≡ 3 (mod 4), then we can take u₀ = 3. Note that if n is prime, these are Mersenne numbers.
• If k = 3: if n ≡ 0 or 3 (mod 4), then u₀ = 5778.
• If k ≡ 1 or 5 (mod 6): if 3 does not divide N, then we take ${\displaystyle u_{0}=(2+{\sqrt {3}})^{k}+(2-{\sqrt {3}})^{k}}$. See below for how to calculate this using a Lucas(4,1) sequence.
• Otherwise, we are in the case where k is a multiple of 3, and it is more difficult to select the right value of u₀.

An alternative method for finding the starting value u₀ is given in Rödseth 1994.[2] 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:

${\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 u₀ from the P value we can use a Lucas(P,1) sequence, as shown in [2] as well as page 124 of.[3] The latter explains that when 3 ∤ k, P=4 may be used, hence the earlier search is not necessary. The starting value u₀ is then equal to the modular Lucas sequence V_k(P,1) 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 N² − 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 ${\displaystyle u_{i}}$. Following the model of the Lucas–Lehmer test, put ${\displaystyle u_{i}=a^{2^{i}}+a^{-2^{i}}}$, and by induction we have ${\displaystyle u_{i}=u_{i-1}^{2}-2}$.

So we can consider ourselves as looking at the 2ⁱth term of the sequence ${\displaystyle v(i)=a^{i}+a^{-i}}$. If a satisfies a quadratic equation, this is a Lucas sequence, and has an expression of the form ${\displaystyle v(i)=\alpha v(i-1)+\beta v(i-2)}$. Really, we're looking at the k ⋅ 2ⁱth 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.

LLR is a program that can run the LLR tests. The program was developed by Jean Penné. Vincent Penné has modified the program so that it can obtain tests via the Internet. The software is both used by individual prime searchers and some distributed computing projects including Riesel Sieve and PrimeGrid.

• Riesel number

• Riesel, Hans (1969). "Lucasian Criteria for the Primality of N = h·2ⁿ − 1". Mathematics of Computation. American Mathematical Society. 23 (108): 869–875. doi:10.2307/2004975. JSTOR 2004975.

• Download Jean Penné's LLR
• Math::Prime::Util::GMP - Part of Perl's ntheory module, this has basic implementations of LLR and Proth form testing, as well as some BLS75 proof methods.