Lucas primality test

Let n be a positive integer. If there exists an integer a, 1 < a < n, such that

:$a^\{n-1\}\backslash \; \backslash equiv\backslash \; 1\; \backslash pmod\; n\; \backslash ,$

and for every prime factor q of n − 1

:$a^\{(\{n-1\})/q\}\backslash \; \backslash not\backslash equiv\backslash \; 1\; \backslash pmod\; n\; \backslash ,$

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:

:$17^\{70\}\backslash \; \backslash equiv\backslash \; 1\; \backslash pmod\; \{71\}.$

For all integers a it is known that

:$a^\{n\; -\; 1\}\backslash equiv\; 1\; \backslash pmod\{n\}\backslash \; \backslash text\{\; if\; and\; only\; if\; \}\; \backslash text\{\; ord\}(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:

:$17^\{35\}\backslash \; \backslash equiv\backslash \; 70\backslash \; \backslash not\backslash equiv\backslash \; 1\; \backslash pmod\; \{71\}$

:$17^\{14\}\backslash \; \backslash equiv\backslash \; 25\backslash \; \backslash not\backslash equiv\backslash \; 1\; \backslash pmod\; \{71\}$

:$17^\{10\}\backslash \; \backslash equiv\backslash \; 1\backslash \; \backslash equiv\backslash \; 1\; \backslash pmod\; \{71\}.$

Unfortunately, we get that 17¹⁰≡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:

:$11^\{70\}\backslash \; \backslash equiv\backslash \; 1\; \backslash 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\}\backslash \; \backslash equiv\backslash \; 70\backslash \; \backslash not\backslash equiv\backslash \; 1\; \backslash pmod\; \{71\}$

:$11^\{14\}\backslash \; \backslash equiv\backslash \; 54\backslash \; \backslash not\backslash equiv\backslash \; 1\; \backslash pmod\; \{71\}$

:$11^\{10\}\backslash \; \backslash equiv\backslash \; 32\backslash \; \backslash not\backslash equiv\backslash \; 1\; \backslash 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]

{{nowrap|if $a^\{n-1\}\; \backslash not\backslash equiv\; 1\; \backslash pmod\; n$ then}}

return composite

else {{nowrap|{{color|gray|#}} $\backslash color\{Gray\}\{a^\{n-1\}\; \backslash equiv\; 1\; \backslash pmod\; n\}$}}

LOOP2: for all prime factors q of n−1:

{{nowrap|if $a^\backslash frac\{n-1\}q\; \backslash not\backslash equiv\; 1\; \backslash pmod\; n$ then}}

if we checked this equality for all prime factors of n−1 then

return prime

else

continue LOOP2

else {{nowrap|{{color|gray|#}} $\backslash color\{Gray\}\{a^\backslash frac\{n-1\}q\; \backslash equiv\; 1\; \backslash pmod\; n\}$}}

continue LOOP1

return possibly composite.

• Édouard Lucas, for whom this test is named
• Fermat's little theorem
• Pocklington primality test, an improved version of this test which only requires a partial factorization of n − 1
• Primality certificate

{{Reflist}}

{{number theoretic algorithms}}

Category:Primality tests