# Fermat’s test

Fermat’s theorem (Fact 2.127) asserts that if n is a prime and a is any integer, 1 < *a <* те—1, thena^{n_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 * _{a}n-i ф i* (

_{mo}q

_{n}) i

_{s ca}iied 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 2^{340} = 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.*

- (i)

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 n
^{2}/^{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 < 10^{15}.