structural:reformatting
Fermat primality test

The simplest probabilistic primality test is the Fermat primality test (actually a compositeness test). It works as follows:

If a (modulo n) is 1 but n is not prime, then n is called a pseudoprime to base a. In practice, if a (modulo n)is 1, then n is usually prime. But here is a counterexample:if n = 341 and a = 2, then

even though 341 = 11·31 is composite. In fact, 341 is the smallest pseudoprime base 2 (see Figure 1 of).

There are only 21853 pseudoprimes base 2 that are less than 2.5 × 10 (see page 1005 of). This means that, for n up to 2.5 × 10, if 2 (modulo n) equals 1, then n is prime, unless n is one of these 21853 pseudoprimes.

Some composite numbers (Carmichael numbers) have the property that a is 1 (modulo n) for every a that is coprime to n. The smallest example is n = 561 = 3·11·17, for which a is 1 (modulo 561) for all a coprime to 561. Nevertheless, the Fermat test is often used if a rapid screening of numbers is needed, for instance in the key generation phase of the RSA public key cryptographic algorithm.