Fermat primality test

Carmichael numbers are rare composite integers satisfying a^(n-1) ≡ 1 (mod n) for all a coprime to n—they pass Fermat’s test despite being composite, exposing the test’s fundamental limitation.

Computational complexity theory classifies problems by difficulty: primality testing is in P (polynomial-time solvable), while factorization’s complexity remains open—conjectured in NP but not P.

The Fermat primality test uses Fermat’s Little Theorem to probabilistically determine primality: if a^(p-1) ≡ 1 (mod p) fails for any a, then p is definitely composite.

A Fermat witness is an integer a that proves n is composite by violating Fermat’s Little Theorem: a^(n-1) ≢ 1 (mod n), definitively establishing n’s non-primality.

The Miller-Rabin primality test strengthens Fermat’s test by examining square roots of unity modulo n, reliably detecting Carmichael numbers and other pseudoprimes that fool simpler tests.

Fast modular exponentiation (square-and-multiply algorithm) computes a^e mod n in O(log e) multiplications rather than O(e), making large-exponent calculations like a^(n-1) mod n tractable for cryptographic-sized numbers.

Primality testing algorithms must efficiently determine whether an input integer is prime or composite, with high accuracy and speed even for large numbers—fundamental to cryptography and number theory.

Determining whether n is prime (primality testing) is computationally much easier than finding n’s prime factors (factorization)—this asymmetry underlies RSA cryptography’s security.

Cryptographic key generation requires efficiently producing large random primes—typically 1024-2048 bits—using iterative testing combining trial division, Fermat/Miller-Rabin tests, and randomness.

Repeating Fermat tests with multiple random bases exponentially reduces error probability—k independent tests yield error probability ≤ 2^(-k) for most composites, enabling controllable confidence levels.