Lucas–Lehmer test

From Wikipedia, the free encyclopedia

This article is about the generalized Lucas–Lehmer test for primality. There is also a Lucas–Lehmer test that only applies to Mersenne numbers; see Lucas–Lehmer test for Mersenne numbers.

In computational number theory, the Lucas–Lehmer test is a primality test for a natural number n; it requires that the prime factors of n − 1 be already known.

If for every prime factor q of n − 1 there exists an integer a less than n and greater than 1 such that firstly

a^{n-1}\ \equiv\ 1 \pmod n

and then

a^{({n-1})/q}\ \not\equiv\ 1 \pmod n

then n is prime. If no such number a can be found, then n is composite number.

For example, take n = 71, n − 1 = 70 = (2)(5)(7). Take a = 11 first:

11^{70}\ \equiv\ 1 \pmod {71}

This does not show that the multiplicative order of 11 mod 71 is 70 because some factor of 70 may also work above. So check 70 divided by its prime factors:

11^{35}\ \equiv\ 70\ \not\equiv\ 1 \pmod {71}
11^{14}\ \equiv\ 54\ \not\equiv\ 1 \pmod {71}
11^{10}\ \equiv\ 32\ \not\equiv\ 1 \pmod {71}

So the multiplicative order of 11 mod 71 is 70, and thus 71 is prime.

To carry out these modular exponentiations, one should always use a fast exponentiation algorithm like binary or addition-chain exponentiation.

The reason for the correctness of the algorithm is as follows: if a survives the first step of the algorithm, we can deduce that a and n are coprime. If a also survives the second step, then the order of a in the group (Z/nZ)* is equal to n − 1, which means that the order of that group is n − 1, implying that n is prime. Conversely, if n is prime, then there exists a primitive root modulo n, and any such primitive root will survive both steps of the algorithm.

[edit] See also

v • d • e
Number-theoretic algorithms
Primality tests
Sieving algorithms
Integer factorization algorithms
Other algorithms
Italics indicate that algorithm is for numbers of special forms; bold indicates deterministic algorithm for primality tests.