Prime Numbers & Primality Testing

Number Theory & Cryptographic Math

Chapter 6 · Prime Numbers & Primality Testing

Chapter 5's modular inverses need gcd(a, n) = 1. The cleanest way to guarantee that is to build n out of prime numbers — and RSA does exactly this. This chapter builds the actual tool real systems use to find primes large enough for cryptography.

What a Prime Actually Is

A prime is an integer greater than 1 whose only positive divisors are 1 and itself. 1 is deliberately excluded by definition — if it counted as prime, numbers wouldn't have a single unique prime factorization (12 = 2×2×3 could also be written 1×2×2×3, 1×1×2×2×3, and so on, endlessly).

Trial Division, Formalized

Chapter 1's own finding-box already used trial division informally. Here's why checking only up to √n is enough, not just a shortcut:

The proof

If n = a × b with a ≤ b, then a cannot be greater than √n — if it were, b ≥ a > √n too, making a × b > n, a contradiction. So if n has any factor at all, its smaller factor is guaranteed to be at most √n. Checking every candidate up to √n is therefore not a heuristic — it's a complete search.

The Sieve of Eratosthenes: Finding Many Primes at Once

Trial division checks one number. To find every prime up to some limit, the Sieve of Eratosthenes is dramatically more efficient: starting from 2, cross out every multiple of each prime found, moving upward.

Verified directly — sieving up to 50

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47 — 15 primes, each confirmed by direct trial division against the same list.

Trial division is the right tool for checking a single already-chosen candidate; the sieve is the right tool for finding many small primes at once — genuinely different jobs, not competing solutions to the same problem.

Why Neither Tool Works at RSA Scale

The scaling wall

Real RSA primes are hundreds of digits long. Even √n for a 600-digit number is still roughly a 300-digit number — trial division up to that point, or sieving a range that large, is completely infeasible, not merely slow, exactly the same wall Chapter 1's own multiply-vs-factor asymmetry described from the attacker's side. Generating primes at cryptographic scale needs a fundamentally different approach.

Probabilistic Primality Testing: Trading Certainty for Speed

Instead of proving primality with total certainty, a probabilistic test checks a property that every prime satisfies, but which most composite numbers fail. A candidate that passes many independent rounds is declared "probably prime," with a failure probability that can be made astronomically small — smaller than the odds of an undetected hardware error corrupting the computation itself.

The starting idea: Fermat's own test

Fermat's Little Theorem (proved fully in Chapter 8) states that for a genuine prime p and any a not divisible by p: a^(p−1) ≡ 1 (mod p). The simplest probabilistic test just checks this directly for a random base a — if it fails, n is definitely composite; if it passes, n is probably prime. Miller-Rabin (the real algorithm production systems use) refines this same core idea with a stronger, harder-to-fool check — its full derivation is beyond this course's own scope, but the underlying trade-off is exactly what's shown here.

Why a Single Test Isn't Enough: A Real Counterexample

Verified directly — 341, the smallest Fermat pseudoprime to base 2

341 = 11 × 31 — genuinely composite. Yet the plain Fermat test with base a=2: 2^340 mod 341 = 1 — it passes, wrongly suggesting 341 might be prime. Testing with other bases catches it immediately: base 3 gives 56, base 5 gives 67, base 7 gives 56 — all correctly fail. A single base can be fooled; this is exactly why real primality testing runs many independent random bases, driving the false-positive probability down exponentially with each additional round.

Real Relevance

Every real-world crypto library — the ones underneath Security's own crypto1 and https1 — generates RSA primes by sieving out small factors quickly, then running many rounds of a probabilistic test (Miller-Rabin in practice) on the survivors. Nothing here is a simplification for teaching purposes; this is genuinely how production key generation works.

Primality Testing in Code

import math

def is_prime_trial(n):
    if n < 2: return False
    for i in range(2, math.isqrt(n) + 1):
        if n % i == 0:
            return False
    return True

def sieve_of_eratosthenes(limit):
    is_prime = [True] * (limit + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, math.isqrt(limit) + 1):
        if is_prime[i]:
            for multiple in range(i*i, limit + 1, i):
                is_prime[multiple] = False
    return [i for i in range(2, limit + 1) if is_prime[i]]

def fermat_test(n, a):
    return pow(a, n - 1, n) == 1   # fast modular exponentiation -- Chapter 7

print(fermat_test(341, 2))   # True -- fooled! 341 is actually composite
print(fermat_test(341, 3))   # False -- correctly catches it

Hands-On Exercises

Exercise 1

Using this chapter's own √n proof, determine the largest candidate divisor that needs to be checked to verify whether n = 221 is prime. Then use trial division up to that bound to determine whether 221 is prime, and if not, name its factors.

📄 View solution

Exercise 2

Using the Sieve of Eratosthenes method from this chapter, find every prime up to 30, showing which multiples get crossed out by each prime as the sieve proceeds (starting with 2, then 3, then 5).

📄 View solution

Exercise 3

Explain, using this chapter's own 341 counterexample, why a real-world crypto library would never trust a single Fermat test with a single fixed base (such as always testing with a=2) when generating RSA primes — and why running the test with several different random bases makes this specific failure far less likely to matter in practice.

📄 View solution

Chapter 6 Quick Reference

Prime: an integer >1 with only 1 and itself as divisors — 1 excluded to preserve unique factorization
Trial division: only needs to check up to √n — proved directly, not just assumed
Sieve of Eratosthenes: the right tool for finding many primes in a range at once, not for checking one large candidate
Both tools are infeasible at RSA's real scale (hundreds-of-digit primes) — the same wall as Chapter 1's own multiply-vs-factor asymmetry
Probabilistic testing (Fermat/Miller-Rabin): trades absolute certainty for speed — a false positive's probability shrinks with each additional random base tested
341 is a real, verified Fermat pseudoprime to base 2 — a single test can be fooled, which is exactly why multiple random bases are used in practice
Next chapter: Modular exponentiation and fast exponentiation