Primality testing: trial division to Miller-Rabin

A prime number is a natural number greater than 1 with only two divisors: 1 and itself. Simple definition, but efficient testing — especially for huge numbers — underpins modern cryptography. This article surveys the algorithms.

Definition

p > 1 whose only divisors are 1 and p:

• Primes — 2, 3, 5, 7, 11, 13, 17, 19, 23, …
• Composites — 4 (2×2), 6 (2×3), 8 (2×4), 9 (3×3), …
• 1 is not prime (special-cased).
• 2 is the only even prime.

Naive trial division

“Try dividing by 2 through n-1”:

function isPrime(n) {
	if (n < 2) return false;
	for (let i = 2; i < n; i++) {
		if (n % i === 0) return false;
	}
	return true;
}

O(n). Slow for large n.

Stop at the square root

If n = a × b with a ≤ b, then a ≤ √n:

function isPrime(n) {
	if (n < 2) return false;
	for (let i = 2; i * i <= n; i++) {
		if (n % i === 0) return false;
	}
	return true;
}

O(√n). Fine for n up to ~10⁶.

6k ± 1 optimization

Apart from 2 and 3, every prime is of the form 6k ± 1:

function isPrime(n) {
	if (n < 2) return false;
	if (n < 4) return true; // 2, 3
	if (n % 2 === 0 || n % 3 === 0) return false;
	for (let i = 5; i * i <= n; i += 6) {
		if (n % i === 0 || n % (i + 2) === 0) return false;
	}
	return true;
}

Tests i = 5, 7, 11, 13, 17, 19, … (step by 6, two checks per step). About 3× faster.

Sieve of Eratosthenes

For “all primes up to N”:

function sieve(n) {
	const isPrime = new Array(n + 1).fill(true);
	isPrime[0] = isPrime[1] = false;
	for (let i = 2; i * i <= n; i++) {
		if (isPrime[i]) {
			for (let j = i * i; j <= n; j += i) {
				isPrime[j] = false;
			}
		}
	}
	return isPrime.map((p, i) => (p ? i : null)).filter((x) => x);
}

Time O(N log log N), space O(N). Enumerates all primes under 10⁶ in milliseconds.

Miller-Rabin (probabilistic)

For huge numbers (e.g., 10²⁰⁰), use a probabilistic test:

n - 1 = 2^r × d  (d odd)

Pick a base a:
x = a^d mod n
If x == 1 or x == n-1 → "probably prime"
Otherwise square x up to r-1 times
If at any point x == n-1 → "probably prime"
Otherwise → composite

Repeating with several bases makes the result certain in practice.

Time O(k log³ n) (k = number of witnesses). 1000-digit numbers in under a second.

AKS primality test (deterministic, polynomial time)

Published in 2002, a major theoretical result:

• Deterministic — never wrong.
• Polynomial time — practical asymptotically.

Constants are large; production code usually still uses Miller-Rabin. The headline result: “primality is in P.”

Mersenne primes

Primes of the form 2^p - 1 (p prime):

• p=2 → 2² - 1 = 3
• p=3 → 2³ - 1 = 7
• p=5 → 2⁵ - 1 = 31
• p=7 → 2⁷ - 1 = 127

A specialized test (Lucas-Lehmer) handles them very fast. The current largest known prime is a Mersenne prime:

• M82589933 = 2^82589933 - 1 (24,862,048 digits, 2018).

GIMPS (Great Internet Mersenne Prime Search) is the distributed-computing project hunting for them.

Twin primes

Primes differing by 2: (3, 5), (5, 7), (11, 13), (17, 19), …

The twin prime conjecture (“infinitely many twin primes”) is open.

Most twins fall on adjacent 6k ± 1 values, but not all 6k ± 1 pairs are twin primes.

Prime number theorem

The count of primes ≤ x:

π(x) ≒ x / ln(x)

Examples:

• x=100 → π(100) = 25 (actual) vs 100/ln(100) ≒ 21.7.
• x=1000 → π(1000) = 168 vs 1000/ln(1000) ≒ 144.8.

Approximation tightens for larger x.

Cryptographic use

RSA key generation:

1. Generate two large primes p, q (512–2048 bits).
2. Compute n = p × q (public).
3. Security relies on the difficulty of factoring n back into p, q.

“Generate a 2048-bit prime” — Miller-Rabin is standard.

Elliptic-curve cryptography (ECC) operates over prime fields too.

Prime distribution

Primes are irregular up close, but show structure at scale:

• Bertrand’s postulate — there’s always a prime between n and 2n.
• Dirichlet’s theorem — infinitely many primes in any arithmetic progression a, a+d, a+2d, … (gcd(a,d)=1).
• Riemann hypothesis (open) — describes prime distribution precisely.

Implementation pitfalls

• Integer overflow — i * i can overflow 32-bit; use BigInt or guard the bound.
• Negatives — primes are positive integers only.
• Memoization — for repeated checks, cache results.
• CSPRNG — for cryptographic prime generation, use a cryptographically secure RNG.

Summary

• Trial division — O(n); square-root cutoff makes it O(√n).
• 6k±1 trims a constant 3×.
• Enumerate with the Sieve of Eratosthenes.
• Miller-Rabin handles huge numbers.
• 2048-bit primes underpin RSA.

To check whether a specific number is prime, the prime checker on this site handles small and moderately large inputs.