# Fermat’s test

Fermat’s theorem (Fact 2.127) asserts that if n is a prime and a is any integer, 1 < a < те—1, thenan_1 = 1 (mod n). Therefore, given an integer n whose primality is under question, finding any integer a in this interval such that this equivalence is not true suffices to prove that n is composite.

4.6 Definition Let n be an odd composite integer. An integer a, 1 < a < n — 1, such that an-i ф i (moq n) is caiied a Fermat witness (to compositeness) for n.

Conversely, finding an integer a between 1 and n — 1 such that a”-1 = 1 (mod n) makes n appear to be a prime in the sense that it satisfies Fermat’s theorem for the base a. This motivates the following definition and Algorithm 4.9.

• 4.7 Definition Let n be an odd composite integer and let a be an integer, 1 < a < n — 1. Then n is said to be a pseudoprime to the base a if a"-1 = 1 (mod те). The integer a is called a Fermat liar (to primality) for n.
• 4.8 Example (pseudoprime) The composite integer n = 341 (= 11 x 31) is a pseudoprime

to the base 2 since 2340 = 1 (mod 341). □

4.9 Algorithm Fermat primality test FERMAT(n,f)

INPUT: an odd integer n > 3 and security parameter t > 1.

OUTPUT: an answer “prime” or “composite” to the question: “Is n prune?”

• 1. For i from 1 to / do the folio whig:
• 1.1 Choose a random integer a, 2 < a < n - 2.
• 1.2 Compute r = a”-1 mod n using Algorithm 2.143.
• 1.3 If г ф 1 then retum(“composite”).
• 2. Retum(“prime”).

If Algorithm 4.9 declares “composite”, then n is certainly composite. On the other hand, if the algorithm declares “prime” then no proof is provided that n is indeed prime. Nonetheless, since pseudoprimes for a given base a are known to be rare, Fermat’s test provides a correct answer on most inputs; this, however, is quite distinct from providing a correct answer most of the time (e.g., if run with different bases) on every input. In fact, it does not do the latter because there are (even rarer) composite numbers which are pseudoprimes to every base a for which gcd(a, ra) = 1.

4.10 Definition A Carmichael number n is a composite integer such that a"-1 = 1 (mod n) for all integers a which satisfy gcd(a, n) = 1.

If n is a Carmichael number, then the only Fermat witnesses for n are those integers a, 1 < a < ?г - 1, for which gcd(a, n) > 1. Thus, if the prime factors of n are all large, then with high probability the Fermat test declares that n is “prime”, even if the number of iterations t is large. This deficiency in the Fermat test is removed in the Solovay-Strassen and Miller-Rabm probabilistic primality tests by relying on criteria which are stronger than Fermat's theorem.

This subsection is concluded with some facts about Carmichael numbers. If the prune factorization of n is known, then Fact 4.11 can be used to easily determine whether n is a Carmichael number.

• 4.11 Fact (necessary> and sufficient conditions for Carmichael numbers) A composite integer n is a Carmichael number if and only if the following two conditions are satisfied:
• (i) n is square-free, i.e., n is not divisible by the square of any prime; and
• (ii) p— 1 divides n - 1 for every prime divisor p of n.

A consequence of Fact 4.11 is the following.

• 4.12 Fact Ever}' Carmichael number is the product of at least three distinct primes.
• 4.13 Fact (bounds for the number of Carmichael numbers)
• (i) There are an infinite number of Carmichael numbers. In fact, there are more than n2/7 Carmichael numbers in the interval [2, n], once n is sufficiently large.
• (ii) The best upper bound known for C(n), the number of Carmichael numbers < n, is:

The smallest Carmichael number is n = 561 = 3 x 11 x 17. Carmichael numbers are relatively scarce; there are only 105212 Carmichael numbers < 1015.