Lucas–Lehmer–Riesel test

In mathematics, the Lucas–Lehmer–Riesel test is a primality test for numbers of the form N = k ⋅ 2ⁿ − 1, with 2ⁿ > 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. The Brillhart–Lehmer–Selfridge test is the fastest deterministic algorithm for numbers of the form N = k ⋅ 2ⁿ + 1 (Proth numbers).

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

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

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

Finding the starting value

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 $u_0 = (2+\sqrt{3})^k+(2-\sqrt{3})^k$ .
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₀

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, 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 $u_i$ . Following the model of the Lucas–Lehmer test, put $u_i = a^{2^i} + a^{-2^i}$ , and by induction we have $u_i = u_{i-1}^2 - 2$ .

So we can consider ourselves as looking at the 2ⁱth term of the sequence $v(i) = a^i + a^{-i}$ . If a satisfies a quadratic equation, this is a Lucas sequence, and has an expression of the form $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 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 both used by individual prime searchers and some distributed computing projects including Riesel Sieve and PrimeGrid.

References

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.

External links

Download Jean Penné's LLR

Number-theoretic algorithms

Primality tests	AKS test APR test Baillie–PSW ECPP test Elliptic curve Pocklington Fermat Lucas Lucas–Lehmer Lucas–Lehmer–Riesel Proth's theorem Pépin's Quadratic Frobenius test Solovay–Strassen Miller–Rabin

Prime-generating	Sieve of Atkin Sieve of Eratosthenes Sieve of Sundaram Wheel factorization

Integer factorization	Continued fraction (CFRAC) Dixon's Lenstra elliptic curve (ECM) Euler's Pollard's rho p − 1 p + 1 Quadratic sieve (QS) General number field sieve (GNFS) Special number field sieve (SNFS) Rational sieve Fermat's Shanks' square forms Trial division Shor's

Multiplication	Ancient Egyptian Long Karatsuba Toom–Cook Schönhage–Strassen Fürer's

Discrete logarithm	Baby-step giant-step Pollard rho Pollard kangaroo Pohlig–Hellman Index calculus Function field sieve

Greatest common divisor	Binary Euclidean Extended Euclidean Lehmer's

Modular square root	Cipolla Pocklington's Tonelli–Shanks

Other algorithms	Chakravala Cornacchia Integer relation Integer square root Modular exponentiation Schoof's

Italics indicate that algorithm is for numbers of special forms Smallcaps indicate a deterministic algorithm