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.[1] [2] It is the basis of the Pratt certificate that gives a concise verification that n is prime.
Let n be a positive integer. If there exists an integer a, 1 < a < n, such that
an-1 \equiv 1\pmodn
and for every prime factor q of n - 1
a({n-1)/q} \not\equiv 1\pmodn
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.
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:
1770 \equiv 1\pmod{71}.
For all integers a it is known that
an\equiv1\pmod{n} ifandonlyiford(a)|(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:
1735 \equiv 70 \not\equiv 1\pmod{71}
1714 \equiv 25 \not\equiv 1\pmod{71}
1710 \equiv 1 \equiv 1\pmod{71}.
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:
1170 \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:
1135 \equiv 70 \not\equiv 1\pmod{71}
1114 \equiv 54 \not\equiv 1\pmod{71}
1110 \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).
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] return composite else LOOP2: for all prime factors q of n-1: if we checked this equality for all prime factors of n-1 then return prime else continue LOOP2 else continue LOOP1 return possibly composite.