Lucas primality test

The Lucas primality test is a method in computational number theory for proving that a natural number n is prime, provided the prime factors of n minus one are already known. The test searches for an integer a between 1 and n such that a raised to the power n minus one is congruent to one modulo n, while a raised to the power of n minus one divided by q is not congruent to one for every prime factor q of n minus one. If such an a exists, n is prime, because a then has multiplicative order n minus one in the group of integers modulo n. If no such a exists, n is either one, two or composite. A failure of the first condition gives a Fermat witness for compositeness. The test underlies the Pratt certificate, a concise proof that a number is prime, and it is named for the nineteenth century mathematician Edouard Lucas. The Pocklington primality test improves on it by needing only a partial factorization of n minus one.