Lucas-Lehmer-Riesel test

From Wikipedia, the free encyclopedia

This article needs additional citations for verification.
Please help improve this article by adding reliable references. Unsourced material may be challenged and removed. (January 2008)

The Lucas-Lehmer-Riesel test is a primality test for numbers of the form $N = k 2 n - 1$ , with $2 n > k$ . The test was developed by Hans Riesel and it is based on the Lucas–Lehmer test for Mersenne numbers.

1 The algorithm
2 Finding the starting value
3 How does the test work?
4 LLR software
5 External links
6 References

[edit] 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$ .

[edit] Finding the starting value

If k is equal to 1, and n is odd, then we are dealing with Mersenne numbers, and can take $u 0 = 4$ .
If $n \equiv 3 \pmod{4}$ , then we can take $u 0 = 3$ .
If $k = 3$ , and n = 0 or 3 mod 4 then $u 0 = 5778$ .
If k = 1 or 5 mod 6 and 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 0$

[edit] How does the test work?

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^2-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) = α v (i - 1) + β v (i - 2)$ . Really, we're looking at the $k \times 2^i$ th term of a different sequence, but since decimations (take every $k$ th 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.

[edit] 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 also used by the distributed computing project Riesel Sieve.

[edit] External links

Download Jean Penné's LLR

[edit] References

Hans Riesel: Lucasian Criteria for the Primality of N = h·2ⁿ - 1. Mathematics of Computation, Vol. 23, No. 108 (Oct. 1969), pp. 869-875, doi:10.2307/2004975

v • d • e Number-theoretic algorithms

Primality tests	AKS · APR · Ballie-PSW · ECPP · Fermat · Lucas–Lehmer · Lucas–Lehmer (Mersenne numbers) · Lucas–Lehmer–Riesel · Proth's theorem · Pépin's · Solovay-Strassen · Miller-Rabin · Trial division

Sieving algorithms	Sieve of Atkin · Sieve of Eratosthenes · Sieve of Sundaram · Wheel factorization

Integer factorization algorithms	CFRAC · Dixon's · ECM · Euler's · Pollard's rho · P - 1 · P + 1 · QS · GNFS · SNFS · rational sieve · Fermat's · Shanks' square forms · Trial division · Shor's algorithm

Other algorithms	Ancient Egyptian multiplication · Aryabhata · Binary GCD · Chakravala · Euclidean · Extended Euclidean · integer relation algorithm · integer square root · Modular exponentiation · Shanks-Tonelli

Italics indicate that algorithm is for numbers of special forms; bold indicates deterministic algorithm for primality tests.