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
formula_1
and for every prime factor "q" of "n" − 1
formula_2
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/"n"Z)*| = "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:
formula_3
For all integers "a" it is known that
formula_4
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:
formula_5
formula_6
formula_7
Unfortunately, we get that 1710≡1 (mod 71). So we still don't know if 71 is prime or not.
We try another random "a", this time choosing "a" = 11. Now we compute:
formula_8
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:
formula_9
formula_10
formula_11
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.
 LOOP1: repeat "k" times:
 pick "a" randomly in the range [2, "n" − 1]
 if formula_12 then
 return "composite"
 else 
 LOOP2: for all prime factors "q" of "n"−1:
 if formula_13 then
 if we checked this equality for all prime factors of "n"−1 then
 return "prime"
 else
 continue LOOP2
 else 
 continue LOOP1
 return "possibly composite".
Notes.
 ;templatestyles src="Reflist/styles.css" / ;