Lucas–Lehmer–Riesel test

Template:Short description Template:More citations needed In mathematics, the Lucas–Lehmer–Riesel test is a primality test for numbers of the form Template:Math with odd Template:Math. 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.Template:Citation needed For numbers of the form Template:Math (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 {{mvar|k}.

Define a sequence Template:Math for all Template:Math by:

$u_i=u_{i-1}^2-2.$

Then Template:Math, with Template:Math, is prime if and only if it divides Template:Math.

Finding the starting value

The starting value Template:Math is determined as follows.

• If Template:Math: if Template:Math and Template:Mvar is even, or Template:Math and Template:Mvar is odd, then Template:Math divides Template:Mvar, and there is no need to test. Otherwise, Template:Math and the Lucas sequence Template:Math may be used: we take $u_0=(2+\sqrt{3}{)}^k+(2-\sqrt{3}{)}^k$, which is the Template:Mvarth term of that sequence. This is a generalization of the ordinary Lucas–Lehmer test, and reduces to it when Template:Math.
• Otherwise, we are in the case where Template:Mvar is a multiple of Template:Math, and it is more difficult to select the right value of Template:Math. It is known that if Template:Math and Template:Math, then we can take Template:Math.

An alternative method for finding the starting value Template:Math is given in Rödseth 1994. The selection method is much easier than that used by Riesel for the 3-divides-Template:Mvar case: first, find a Template:Mvar-value that satisfies the following equalities of Jacobi symbols:

$\left(\frac{P-2}{N}\right)=1\text{and}\left(\frac{P+2}{N}\right)=-1.$

In practice, only a few Template:Mvar-values need be checked before one is found (5, 8, 9, or 11 work in about 85% of trials).Template:Citation needed

To find the starting value Template:Math from the Template:Mvar value, we can use a Lucas Template:Math sequence, as shown in as well as page 124 of. The latter explains that when Template:Math, Template:Math may be used as above, and no further search is necessary.

The starting value Template:Math will be the Lucas sequence term Template:Math taken modulo Template:Mvar. 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 Template:Mvar, we work in the multiplicative group of a quadratic extension of the integers modulo Template:Mvar; if Template:Mvar is prime, then the order of this multiplicative group is Template:Math, it has a subgroup of order Template:Math, and we try to find a generator for that subgroup.

We start off by trying to find a non-iterative expression for the Template:Math. Following the model of the Lucas–Lehmer test, put Template:Math, and by induction we have Template:Math.

So we can consider ourselves as looking at the Template:Mathth term of the sequence Template:Math. If Template:Mvar satisfies a quadratic equation, then this is a Lucas sequence, and has an expression of the form Template:Math. Really, we are looking at the Template:Mathth term of a different sequence, but since decimations (take every Template:Mvarth term starting with the zeroth) of a Lucas sequence are themselves Lucas sequences, we can deal with the factor Template:Mvar by picking a different starting point.

LLR software

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 used by both individual prime searchers and some distributed computing projects including Riesel Sieve and PrimeGrid.

A revised version, LLR2 was deployed in 2020. This generates a "proof of work" certificate which allows the computation to be verified without needing a full double-check.

A further update, PRST uses an alternate certificate scheme which takes longer to verify but is faster to generate for some forms of prime.

See also

• Riesel number

References

• Template:Cite journal

External links

• 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.