Lucas primality test

Concepts

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

a n − 1   ≡   1 ( mod n )

and for every prime factor q of n − 1

a ( n − 1 ) / q   ≢   1 ( mod n )

then n is prime. If no such number a exists, then n is either 1 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 ) .

For all integers a it is known that

a n − 1 ≡ 1 ( mod n )    if and only if   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   ≡   70   ≢   1 ( mod 71 ) 17 14   ≡   25   ≢   1 ( mod 71 ) 17 10   ≡   1   ≡   1 ( mod 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   ≡   1 ( mod 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 ) 11 14   ≡   54   ≢   1 ( mod 71 ) 11 10   ≡   32   ≢   1 ( mod 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:

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 a n − 1 ≢ 1 ( mod n ) then return composite else # a n − 1 ≡ 1 ( mod n ) LOOP2: for all prime factors q of n−1: if a n − 1 q ≢ 1 ( mod n ) then if we checked this equality for all prime factors of n−1 then return prime else continue LOOP2 else # a n − 1 q ≡ 1 ( mod n ) continue LOOP1 return possibly composite.