Helpful context:

RSA requires two large primes. Not small ones - generating secure 2048-bit RSA keys means working with primes near $2^{1024}$, each roughly 300 decimal digits long. There is no closed-form formula for primes of that size. The standard approach is: generate a random odd number, test if it is prime, repeat until you succeed. For this to be practical, primality testing must be fast.

The naive approach - trial division up to $\sqrt{n}$ - is completely infeasible. For a 1024-bit number, $\sqrt{n} \approx 2^{512}$, and checking each potential divisor would require more operations than atoms in the observable universe. The clever approach is probabilistic: use number theory to test a condition that all primes satisfy but few composites do. Each test round drives down the probability of error exponentially. After 40 rounds, the error probability is less than $2^{-80}$, negligible for any application.

The deepest result in the area, AKS (2002), proved that primality can be decided deterministically in polynomial time. That was a theoretical landmark. Practically, Miller-Rabin with 40 rounds is faster, simpler, and sufficient.

Trial Division

The simplest test: to check if $n$ is prime, divide by every integer from 2 to $\sqrt{n}$.

Why $\sqrt{n}$ suffices. If $n = ab$ with $a \leq b$, then $a \leq \sqrt{n}$. So if $n$ has any factor other than 1 and itself, it has one at most $\sqrt{n}$.

Cost. $O(\sqrt{n})$ divisions. For a 1024-bit number, $\sqrt{n} \approx 2^{512} \approx 10^{154}$. A computer doing $10^{12}$ divisions per second would take $10^{142}$ seconds. The age of the universe is about $4 \times 10^{17}$ seconds. Trial division is not an option for cryptographic inputs.

When trial division is used. As a first pass: check divisibility by all primes up to $10^6$ or so. If none divide $n$, proceed to a faster test. This eliminates many composites cheaply.

The Fermat Primality Test

Motivation. Fermat’s little theorem says: if $p$ is prime and $\gcd(a, p) = 1$, then $a^{p-1} \equiv 1 \pmod p$. The contrapositive: if $a^{n-1} \not\equiv 1 \pmod n$, then $n$ is not prime (or $a$ shares a factor with $n$).

Algorithm.

  1. Pick a random $a \in \{2, \ldots, n-2\}$.
  2. Compute $a^{n-1} \bmod n$ using fast exponentiation ($O(\log n)$ multiplications).
  3. If $a^{n-1} \not\equiv 1 \pmod n$: output composite.
  4. If $a^{n-1} \equiv 1 \pmod n$: output probably prime.

When the test can be wrong. The test can say “probably prime” when $n$ is composite. The value $a$ is a Fermat witness for compositeness if $a^{n-1} \not\equiv 1 \pmod n$. A composite $n$ for which $a^{n-1} \equiv 1 \pmod n$ is called a Fermat pseudoprime to the base $a$.

Carmichael Numbers

A Carmichael number is a composite $n$ such that $a^{n-1} \equiv 1 \pmod n$ for every $a$ with $\gcd(a, n) = 1$. The Fermat test fails completely for Carmichael numbers: no choice of $a$ coprime to $n$ will ever certify the compositeness of $n$.

The smallest Carmichael number is $561 = 3 \times 11 \times 17$.

Korselt’s criterion. A squarefree integer $n > 1$ is Carmichael if and only if $(p - 1) \mid (n - 1)$ for every prime factor $p$ of $n$.

Verification for $561$: $n - 1 = 560$. The prime factors are 3, 11, 17 with $p - 1$ values 2, 10, 16. Check: $2 \mid 560$, $10 \mid 560$, $16 \mid 560$. All hold. So 561 is Carmichael.

There are infinitely many Carmichael numbers (Alford-Granville-Pomerance, 1994). The Fermat test is not safe for production use.

The Miller-Rabin Test

The Miller-Rabin test is a strengthened version of the Fermat test that detects Carmichael numbers. It is the standard primality test used in cryptographic libraries.

Setup. For an odd $n > 2$, write $n - 1 = 2^s d$ where $d$ is odd and $s \geq 1$ (factor out all 2s from $n - 1$).

Strong pseudoprime condition. We say $n$ is a strong pseudoprime to base $a$ if either:

  1. $a^d \equiv 1 \pmod n$, or
  2. $a^{2^r d} \equiv -1 \pmod n$ for some $r \in \{0, 1, \ldots, s-1\}$.

Algorithm.

  1. Write $n - 1 = 2^s d$ with $d$ odd.
  2. Pick random $a \in \{2, \ldots, n-2\}$.
  3. Compute $x = a^d \bmod n$.
  4. If $x = 1$ or $x = n - 1$: pass (go to step 8).
  5. Repeat $s - 1$ times: $x \leftarrow x^2 \bmod n$. If $x = n - 1$: pass (go to step 8).
  6. Output composite.
  7. (Step 8): Output probably prime.

Why primes always pass. If $p$ is prime, then $(\mathbb{Z}/p\mathbb{Z})^\times$ has order $p-1 = 2^s d$. By Fermat, $a^{p-1} \equiv 1$. The sequence $a^d, a^{2d}, a^{4d}, \ldots, a^{2^s d}$ ends at 1. The first 1 must be preceded by $-1$ (since if $x^2 \equiv 1 \pmod p$ and $p$ is prime, then $p \mid (x-1)(x+1)$, so $x \equiv 1$ or $x \equiv -1$). So either $a^d \equiv 1$ or somewhere in the squaring sequence we hit $-1$. A prime always satisfies one of the two conditions.

Why the test rejects most composite witnesses. For a composite $n$ with no prime factor less than some threshold, at most $1/4$ of bases $a \in \{1, \ldots, n-1\}$ are non-witnesses (i.e., satisfy the strong pseudoprime condition despite $n$ being composite). This bound, due to Rabin (1980), is tight.

Error probability with $k$ independent tests. Run Miller-Rabin with $k$ independent random bases. If $n$ is composite, each test catches it with probability at least $3/4$. The probability that all $k$ tests fail is at most $(1/4)^k = 4^{-k}$.

For $k = 40$: error probability $\leq 4^{-40} = 2^{-80}$. For $k = 128$: $2^{-256}$. In practice, $k = 40$ is the standard.

Comparison with Fermat Test

Property Fermat test Miller-Rabin
Correctly rejects all primes Yes Yes
Can fail on Carmichael numbers Yes (completely) No (detects them)
Error rate per test Can be 1 for Carmichael At most $1/4$
Cost per test $O(\log n)$ multiplications $O(\log n)$ multiplications

Miller-Rabin is strictly better than Fermat. There is no reason to use the Fermat test in practice.

Deterministic Miller-Rabin

For small inputs, the set of bases needed to make Miller-Rabin deterministic is known precisely.

Under GRH. Assuming the Generalized Riemann Hypothesis, testing all bases $a \leq 2(\ln n)^2$ suffices to give a deterministic decision for any $n$.

Unconditional results for bounded $n$. For practical ranges, finite sets of bases have been determined:

Range Sufficient bases
$n < 2{,}047$ $\{2\}$
$n < 1{,}373{,}653$ $\{2, 3\}$
$n < 3{,}215{,}031{,}751$ $\{2, 3, 5\}$
$n < 3.3 \times 10^{24}$ $\{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41\}$
$n < 3.3 \times 10^{24}$ 13 bases above

For integers up to about $3.3 \times 10^{24}$, testing the 13 bases $\{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41\}$ gives a proven correct deterministic result. This covers 80-bit numbers and is used in some cryptographic libraries.

For larger cryptographic inputs (512-bit, 1024-bit, 2048-bit), the probabilistic version with $k = 40$ is used in practice.

The AKS Primality Test

Theorem (Agrawal-Kayal-Saxena, 2002). There is a deterministic polynomial-time algorithm for primality testing.

Before AKS, primality testing was either probabilistic (Miller-Rabin) or relied on unproven assumptions (GRH). AKS settled the theoretical question: PRIMES is in P.

The AKS condition. The test is based on the identity: $n$ is prime if and only if $(x + a)^n \equiv x^n + a \pmod{n}$ in $\mathbb{Z}[x]/(x^r - 1)$ for appropriate $r$ and all $a$ in a certain range. For a composite, this polynomial identity fails for at least one such $a$.

Complexity. The original AKS paper proved $O((\log n)^{12})$. Subsequent improvements by Lenstra and Bernstein reduced this to $O((\log n)^{6+\varepsilon})$ under standard conjectures.

Practical status. AKS is a theoretical landmark. Practically, Miller-Rabin with 40 rounds is orders of magnitude faster, and the error probability $2^{-80}$ is so small that it is not a concern for any real application. No cryptographic library uses AKS in production.

Prime Generation in Practice

Strategy. To generate a random $k$-bit prime:

  1. Generate a random $k$-bit odd integer $n$ (set the top bit to ensure it’s exactly $k$ bits, set the low bit to ensure it’s odd).
  2. Run trial division against small primes (2, 3, 5, …, up to $10^4$ or so) to quickly eliminate obvious composites.
  3. Run Miller-Rabin with $k = 40$ random bases.
  4. If the number passes all tests, it is prime with probability exceeding $1 - 2^{-80}$.
  5. If it fails any test, repeat from step 1.

How many trials? By the Prime Number Theorem, the density of primes near $x$ is approximately $1 / \ln x$. For a random $k$-bit number, $x \approx 2^k$ and $\ln x \approx k \ln 2 \approx 0.693k$. Expected number of candidates to test: approximately $0.693k / 2 \approx 0.35k$ (dividing by 2 because we only test odd numbers).

For a 1024-bit prime: roughly $0.35 \times 1024 \approx 356$ candidates expected. For 2048-bit: roughly 712.

Each Miller-Rabin test. $O(\log n)$ modular multiplications, each costing $O(k^2)$ bit operations. Total per candidate: $O(k^3)$ bit operations. For $k = 2048$ and 40 bases, each test involves $40 \times 2048 \approx 80,000$ multiplications of 2048-bit numbers. Modern hardware handles this in milliseconds.

Total cost. For a 2048-bit prime: roughly $712 \times 40$ rounds of modular squaring and multiplication. Milliseconds on modern hardware.

Summary

Method Deterministic Error Cost per test Notes
Trial division Yes None $O(\sqrt{n})$ Infeasible for large $n$
Fermat test No Can be 1 (Carmichael) $O(\log n)$ mults Fails completely on Carmichael numbers
Miller-Rabin No (probabilistic) $\leq 4^{-k}$ for $k$ rounds $O(k \log n)$ mults Standard in practice
Deterministic MR Yes (bounded $n$) None Fixed set of bases Correct for $n < 3.3 \times 10^{24}$
AKS Yes None $O((\log n)^{6+\varepsilon})$ Theoretical; not used in production

For prime generation in practice: random odd number, trial division sieve, then Miller-Rabin with 40 rounds. Expected number of candidates: $O(k)$ for $k$-bit primes. Total time: milliseconds for 2048-bit primes.

Read next: