Fermat primality test

The Fermat primality test is a probabilistic method for deciding whether a number is probably prime. It rests on Fermat's little theorem, which says that if p is prime and a is not divisible by p, then a raised to the power p minus one leaves remainder one when divided by p. To test a number n, the method picks random bases a and checks that congruence. If it fails for any base, a is a Fermat witness and n is certainly composite. If it holds, n is only probably prime, and a composite number that passes for a base is called a Fermat pseudoprime to that base, with the base a Fermat liar. With fast modular exponentiation and multiplication the running time is about k times the square of the logarithm of n, where k is the number of random bases tried. Carmichael numbers, which fool every coprime base, are a known flaw, so stronger relatives such as the Miller-Rabin and Baillie-PSW tests are preferred in practice.