Pseudoprime

A pseudoprime to a base a is a composite number n with gcd(a,n)=1 such that a^(n−1) ≡ 1 (mod n). Such numbers satisfy Fermat's little theorem for that base and can fool simple primality tests that rely only on Fermat's criterion.

For example, 341 = 11 × 31 is a Fermat pseudoprime to base 2, since 2^340 ≡ 1 (mod 341). 561 = 3 × 11 × 17 is a Carmichael number: a Fermat pseudoprime to every base a with gcd(a,561)=1.

Carmichael numbers are a subset of pseudoprimes with the stronger property of being Fermat pseudoprimes for all bases coprime to n. Korselt's criterion characterizes them, and there are infinitely many Carmichael numbers.

Strong pseudoprimes to a base a are composites that pass the Miller-Rabin test for that base. Such numbers exist, but they are relatively rare; using several bases makes the chance of a false prime negligibly small.

In practice, the existence of pseudoprimes highlights the need for stronger primality tests in cryptography, and the study of pseudoprimes informs the design and analysis of these algorithms.