Lucas-Lehmer Test
Alternate name
Definition
The Lucas-Lehmer test is an efficient deterministic primality test for determining if a Mersenne number M_n is prime. Since it is known that Mersenne numbers can only be prime for prime subscripts, attention can be restricted to Mersenne numbers of the form M_p = 2^p - 1, where p is an odd prime. Consider the recurrence equation s_n congruent s_(n - 1)^2 - 2 (mod M_p) with s_0 congruent 4. For example, ignoring the congruence, the first few terms of this iteration are 4, 14, 194, 37634, 1416317954, ... (OEIS A003010). It turns out that M_p is prime iff s_(p - 2) congruent 0 (mod M_p), and the value s_(p - 2) (mod M_p) is called the Lucas-Lehmer residue for p.
Related terms
Associated people
