The Lucas-Lehmer test is an efficient deterministic primality test for determining if a Mersenne
number 
is prime. Since Mersenne
numbers can only be prime for prime indices, attention can be restricted to Mersenne
numbers of the form 
, where 
is an odd prime.
Consider the recurrence equation
 |
(1)
|
with 
.
For example, ignoring the congruence, the first few
terms of this iteration are 4, 14, 194, 37634, 1416317954, ... (OEIS A003010).
It turns out that 
is prime iff 
, and the value 
is called the Lucas-Lehmer residue for 
.
For example, the sequence obtained for 
is given by 4, 14, 67, 42, 111, 0, so 
is prime.
Including the value 1 for 
from 
, the first few Lucas-Lehmer residues for prime
number exponents are 1, 0, 0, 0, 1736, 0, 0, 0, 6107895, 458738443, 0, 117093979072,
... (OEIS A095847).
For general integers, Pratt (1975) developed recursive primality certification using the prime factorization
of 
.
The resulting certification is known as a Pratt
certificate.
A related 
primality test for an odd
number 
starts with the complete prime factorization
 |
(2)
|
with 
the distinct prime factors, and 
their respective positive
integer exponents. If there exists a Lucas
sequence 
with integer parameters 
, 
and 
, where 
, such that
 |
(3)
|
for 
,
..., 
and
 |
(4)
|
then 
is a prime number (Brillhart et al. 1975,
Ribenboim 2004).
." Math. Comput. 29, 620-647, 1975.