In mathematics, the Lucas–Lehmer–Riesel test is a

primality test A primality test is an algorithm for determining whether an input number is prime. Among other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating wheth ...

for numbers of the form with odd . 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 ( Proth numbers), either application of Proth's theorem (a

Las Vegas algorithm In computing, a Las Vegas algorithm is a randomized algorithm that always gives Correctness (computer science), correct results; that is, it always produces the correct result or it informs about the failure. However, the runtime of a Las Vegas alg ...

) or one of the deterministic proofs described in Brillhart–Lehmer–Selfridge 1975 (see

Pocklington primality test In mathematics, the Pocklington–Lehmer primality test is a primality test devised by Henry Cabourn Pocklington and Derrick Henry Lehmer. The test uses a partial factorization of N - 1 to prove that an integer N is prime. It produces a pri ...

) 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 . Define a sequence for all by: :

u_i = u_^2-2.

Then , with , is prime if and only if it divides .

Finding the starting value

The starting value is determined as follows. * If : if and is even, or and is odd, then divides , and there is no need to test. Otherwise, and the

Lucas sequence In mathematics, the Lucas sequences U_n(P,Q) and V_n(P, Q) are certain constant-recursive integer sequences that satisfy the recurrence relation : x_n = P \cdot x_ - Q \cdot x_ where P and Q are fixed integers. Any sequence satisfying this rec ...

may be used: we take

u_0 = (2+\sqrt)^k+(2-\sqrt)^k

, which is the th term of that sequence. This is a generalization of the ordinary Lucas–Lehmer test, and reduces to it when . * Otherwise, we are in the case where is a multiple of , and it is more difficult to select the right value of . It is known that if and , then we can take . An alternative method for finding the starting value is given in Rödseth 1994. The selection method is much easier than that used by Riesel for the 3-divides- case: first, find a -value that satisfies the following equalities of Jacobi symbols: :

\left(\frac\right)=1 \quad\text\quad \left(\frac\right)=-1.

In practice, only a few -values need be checked before one is found (5, 8, 9, or 11 work in about 85% of trials). To find the starting value from the value, we can use a Lucas sequence, as shown in as well as page 124 of. The latter explains that when , may be used as above, and no further search is necessary. The starting value will be the

term taken modulo . 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 , we work in the multiplicative group of a quadratic extension of the integers modulo ; if is prime, then the order of this multiplicative group is , it has a subgroup of order , and we try to find a generator for that subgroup. We start off by trying to find a non-iterative expression for the . Following the model of the Lucas–Lehmer test, put , and by induction we have . So we can consider ourselves as looking at the th term of the sequence . If satisfies a quadratic equation, then this is a Lucas sequence, and has an expression of the form . Really, we are looking at the th term of a different sequence, but since decimations (take every th term starting with the zeroth) of a Lucas sequence are themselves Lucas sequences, we can deal with the factor 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 Distributed computing is a field of computer science that studies distributed systems, defined as computer systems whose inter-communicating components are located on different networked computers. The components of a distributed system commu ...

projects including

Riesel Sieve PrimeGrid is a volunteer computing project that searches for very large (up to world-record size) prime numbers whilst also aiming to solve long-standing mathematical conjectures. It uses the Berkeley Open Infrastructure for Network Computing (BO ...

and

PrimeGrid PrimeGrid is a volunteer computing project that searches for very large (up to world-record size) prime numbers whilst also aiming to solve long-standing mathematical conjectures. It uses the Berkeley Open Infrastructure for Network Computing ( ...

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

References

External links