In computational number theory, the Lucas test is a primality test for a natural number n; it requires that the prime factors of n − 1 be already known. It is the basis of the Pratt certificate that gives a concise verification that n is prime.
Concepts Let n be a positive integer. If there exists an integer a, 1 < a < n, such that
a n − 1 ≡ 1 ( mod n ) {\displaystyle a^{n-1}\ \equiv \ 1{\pmod {n}}\,}
and for every prime factor q of n − 1
a ( n − 1 ) / q ≢ 1 ( mod n ) {\displaystyle a^{({n-1})/q}\ \not \equiv \ 1{\pmod {n}}\,}
then n is prime. If no such number a exists, then n is either 1, 2, or composite. The reason for the correctness of this claim is as follows: if the first equivalence holds for a, 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 (because the order of every element of a group divides the order of the group), implying that n is prime. Conversely, if n is prime, then there exists a primitive root modulo n, or generator of the group (Z/nZ)*. Such a generator has order |(Z/nZ)*| = n − 1 and both equivalences will hold for any such primitive root. Note that if there exists an a < n such that the first equivalence fails, a is called a Fermat witness for the compositeness of n.
Example For example, take n = 71. Then n − 1 = 70 and the prime factors of 70 are 2, 5 and 7. We randomly select an a = 17 < n. Now we compute:
17 70 ≡ 1 ( mod 71 ) . {\displaystyle 17^{70}\ \equiv \ 1{\pmod {71}}.}
For all integers a it is known that
a n − 1 ≡ 1 ( mod n ) if and only if ord ( a ) ∣ ( n − 1 ) . {\displaystyle a^{n-1}\equiv 1{\pmod {n}}\ {\text{ if and only if }}{\text{ ord}}(a)\mid (n-1).}
Therefore, the multiplicative order of 17 (mod 71) is not necessarily 70 because some factor of 70 may also work above. So check 70 divided by its prime factors:
17 35 ≡ 70 ≢ 1 ( mod 71 ) {\displaystyle 17^{35}\ \equiv \ 70\ \not \equiv \ 1{\pmod {71}}}
17 14 ≡ 25 ≢ 1 ( mod 71 ) {\displaystyle 17^{14}\ \equiv \ 25\ \not \equiv \ 1{\pmod {71}}}
17 10 ≡ 1 ≡ 1 ( mod 71 ) . {\displaystyle 17^{10}\ \equiv \ 1\ \equiv \ 1{\pmod {71}}.}
Unfortunately, we get that 1710 ≡ 1 (mod 71). So we still do not know if 71 is prime or not. We try another random a, this time choosing a = 11. Now we compute:
11 70 ≡ 1 ( mod 71 ) . {\displaystyle 11^{70}\ \equiv \ 1{\pmod {71}}.}
Again, this does not show that the multiplicative order of 11 (mod 71) is 70 because some factor of 70 may also work. So check 70 divided by its prime factors:
11 35 ≡ 70 ≢ 1 ( mod 71 ) {\displaystyle 11^{35}\ \equiv \ 70\ \not \equiv \ 1{\pmod {71}}}
11 14 ≡ 54 ≢ 1 ( mod 71 ) {\displaystyle 11^{14}\ \equiv \ 54\ \not \equiv \ 1{\pmod {71}}}
11 10 ≡ 32 ≢ 1 ( mod 71 ) . {\displaystyle 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 could use a fast exponentiation algorithm like binary or addition-chain exponentiation).
Algorithm The algorithm can be written in pseudocode as follows:
algorithm lucas_primality_test is input: n > 2, an odd integer to be tested for primality. k, a parameter that determines the accuracy of the test. output: prime if n is prime, otherwise composite or possibly composite.
determine the prime factors of n−1.
… excerpt ends here. Continue reading the full article.
