Fermat primality test

The Fermat primality test is a probabilistic test to determine whether a number is a probable prime. Fermat's little theorem states that if p is prime and a is not divisible by p, then If one wants to test whether p is prime, then we can pick random integers a not divisible by p and see whether the congruence holds. If it does not hold for a value of a, then p is composite. This congruence is unlikely to hold for a random a if p is composite. Therefore, if the equality does hold for one or more values of a, then we say that p is probably prime. However, note that the above congruence holds trivially for , because the congruence relation is compatible with exponentiation. It also holds trivially for if p is odd, for the same reason. That is why one usually chooses a random a in the interval . Any a such that when n is composite is known as a Fermat liar. In this case n is called Fermat pseudoprime to base a. If we do pick an a such that then a is known as a Fermat witness for the compositeness of n. Suppose we wish to determine whether n = 221 is prime. Randomly pick 1 < a < 220, say a = 38. We check the above congruence and find that it holds: Either 221 is prime, or 38 is a Fermat liar, so we take another a, say 24: So 221 is composite and 38 was indeed a Fermat liar. Furthermore, 24 is a Fermat witness for the compositeness of 221. The algorithm can be written as follows: Inputs: n: a value to test for primality, n>3; k: a parameter that determines the number of times to test for primality Output: composite if n is composite, otherwise probably prime Repeat k times: Pick a randomly in the range [2, n − 2] If , then return composite If composite is never returned: return probably prime The a values 1 and n-1 are not used as the equality holds for all n and all odd n respectively, hence testing them adds no value. Using fast algorithms for modular exponentiation and multiprecision multiplication, the running time of this algorithm is O(k log2n log log n) = Õ(k log2n), where k is the number of times we test a random a, and n is the value we want to test for primality; see Miller–Rabin primality test for details.