Skip to main content

Primality Tests

Algorithms to decide whether an integer is prime. From exact trial division to fast probabilistic / deterministic Miller–Rabin.

This lesson follows CP-Algorithms — Primality tests.

Related: Integer Factorization, Montgomery Multiplication, Divisor Functions.

Trial division​

A composite n has a divisor d with 2 ≤ d ≤ √n (because if every proper divisor were > √n, the cofactor would be < √n). Scan d = 2 … ⌊√n⌋; any hit ⇒ composite.

bool isPrime(int x) {
    for (int d = 2; d * d <= x; d++) {
        if (x % d == 0)
            return false;
    }
    return x >= 2;
}

Optimize by special-casing 2 and only testing odd d (or a wheel) — same ideas as in Integer Factorization.

🧪 Trial division demo

Fermat primality test​

Fermat’s little theorem: if p is prime and gcd(a,p)=1, then

a^{p−1} ≡ 1  (mod p)

Pick 2 ≤ a ≤ n−2. If a^{n−1} ≢ 1 (mod n), then a is a Fermat witness — n is composite.

If the congruence holds, n is only probably prime: a might be a Fermat liar. Repeat with random bases.

bool probablyPrimeFermat(int n, int iter = 5) {
    if (n < 4)
        return n == 2 || n == 3;
    for (int i = 0; i < iter; i++) {
        int a = 2 + rand() % (n - 3);
        if (binpower(a, n - 1, n) != 1)
            return false;
    }
    return true;
}

Use binary exponentiation for a^{n−1} mod n.

Carmichael numbers​

Some composites satisfy a^{n−1} ≡ 1 (mod n) for every a coprime to n — e.g. 561 = 3·11·17. Fermat catches them only if you luck into gcd(a,n) ≠ 1. There are only 646 Carmichael numbers below 10⁹, so Fermat is still used when you need raw speed.

Miller–Rabin​

Write odd n−1 = 2^s · d with d odd. Factor Fermat’s congruence:

a^{n−1} − 1 = (a^{2^{s−1}d} + 1) ⋯ (a^d + 1)(a^d − 1)

If n is prime it must divide one factor. For base a, check whether

a^d ≡ 1 (mod n)

or

a^{2^r d} ≡ −1 (mod n)   for some  0 ≤ r ≤ s−1

If neither holds, a is a witness (proven composite). Otherwise a is a strong liar / n is a strong probable prime.

Unlike Carmichael numbers, at most 1/4 of bases can be strong liars. Each random iteration has ≥ 75% chance to catch a composite.

🧪 Deterministic Miller–Rabin (64-bit bases)

Speed tip​

Before MR, trial-divide by the first few primes. About 88% of integers have a prime factor < 100.

Deterministic Miller–Rabin​

Miller: bases ≤ O((ln n)²) suffice. Bach: a ≤ 2 (ln n)².

Practical tables (no randomness):

RangeBases
32-bit2, 3, 5, 7 (smallest fail: 3 215 031 751)
64-bitfirst 12 primes: 2…37
64-bit (7 bases)2, 325, 9375, 28178, 450775, 9780504, 1795265022 — also exclude prime factors of those bases
bool MillerRabin(u64 n) {
    if (n < 2) return false;
    int r = 0;
    u64 d = n - 1;
    while ((d & 1) == 0) { d >>= 1; r++; }
    for (int a : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) {
        if (n == a) return true;
        if (check_composite(n, a, d, r)) return false;
    }
    return true;
}

Check: primality tests​

Quiz

Primality tests

1 / 5

Trial division only needs to check divisors up to…

Pick an answer to see if you are right.

Practice drills​

Activity: Trial is-prime

Input: integer n (0 ≤ n ≤ 10⁶). Print 1 if prime, else 0.

Practice problems​

From CP-Algorithms:

Cheat sheet​

TestKindNotes
Trial divisionDeterministicO(√n); fine for small n
FermatProbabilisticFast; Carmichael liars
Miller–RabinProbabilisticError ≤ 4^{−k} with k rounds
MR + fixed basesDeterministic32/64-bit tables
Pre-filter—Trial tiny primes first