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 there exists some a less than n and greater than 1 such that firstly
and then
for all prime factors q of n − 1, 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:
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:
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 the fast method of exponentiating by squaring.
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.
