Lucas-Lehmer primality test
|
|
The Lucas-Lehmer primality test is a method of testing the primality of some number n; it requires that the prime factors of n-1 be known.
If there exists some a less than n and greater than 1 such that firstly
- <math>a^{n-1}\ \equiv\ 1 \pmod n<math>
and then
- <math>a^{({n-1})/q}\ \not\equiv\ 1 \pmod n<math>
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:
- <math>11^{70}\ \equiv\ 1 \pmod {71}<math>
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:
- <math>11^{35}\ \equiv\ 70\ \not\equiv\ 1 \pmod {71}<math>
- <math>11^{14}\ \equiv\ 54\ \not\equiv\ 1 \pmod {71}<math>
- <math>11^{10}\ \equiv\ 32\ \not\equiv\ 1 \pmod {71}<math>
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 primite root modulo n, and any such primitive root will survive both steps of the algorithm.