Testing the primality of a large number

Recognising a prime is easy when the number is small. For a 300-digit number the question becomes an algorithmic problem — and its answer underpins modern cryptography.

The cost of the naive test

Testing every divisor up to √n takes about √n divisions:

n = 10⁶      ->  1,000 divisions         instantaneous
n = 10¹⁸     ->  10⁹ divisions           a few seconds
n = 10⁶⁰⁰    ->  10³⁰⁰ divisions         beyond the age of the universe

But RSA keys use 300-digit primes. A test that looks for no divisor at all is needed.

Fermat's little theorem

If p is prime and a is not divisible by p, then a^(p-1) ≡ 1 (mod p).

The idea: this equality is easy to check — fast modular exponentiation computes it in a few hundred operations, even on 300 digits. If it fails, n is certainly composite.

n = 15,  a = 2 :   2¹⁴ mod 15 = 4  ≠ 1     ->  15 is COMPOSITE, for certain

Remarkable: we have proved 15 composite without finding any of its factors. The test detects compositeness without factorisation — exactly what is needed.

The pseudoprime trap

The converse is false. Some composites pass the test:

n = 341 = 11 × 31,  a = 2 :   2³⁴⁰ mod 341 = 1        ->  test PASSED
                                                          yet composite

341 is a base-2 pseudoprime. Trying another base exposes it (3³⁴⁰ mod 341 ≠ 1). But worse exists: the Carmichael numbers (561, 1105, 1729…) pass the test for every base coprime to them.

Miller-Rabin: the test used in practice

It refines Fermat's by exploiting an extra property of square roots of 1 modulo a prime, which neutralises Carmichael numbers.

Probabilistic test:
   - if n fails for one base   ->  n is COMPOSITE, with certainty
   - if n passes for k bases   ->  n is prime with an error probability
                                   below 4^(-k)

k = 20 bases  ->  error probability < 10⁻¹²
k = 40 bases  ->  < 10⁻²⁴, less likely than a hardware fault in the processor

This is what your browser does, in a few milliseconds, every time it opens a secure connection. A deterministic polynomial-time test has existed since 2002 — the AKS algorithm — but it remains slower in practice: Miller-Rabin is still preferred.

The asymmetry that protects your communications

Multiplying two 300-digit primes           ->  microseconds
Testing whether a 300-digit number is prime -> milliseconds
FACTORING a 600-digit product              ->  no known algorithm
                                                in reasonable time

That is the whole idea of RSA: we can build and verify easily, but not undo. The public factoring record stands at 250 digits, achieved in 2020 after some 2,700 core-years of computation.

Two honest caveats, however:

• nothing proves factoring is intrinsically hard; a fast algorithm could be found tomorrow;
• Shor's algorithm factors in polynomial time on a quantum computer. No machine of sufficient size exists today, but this is what drives post-quantum cryptography.

Summary

• Testing divisors up to √n is unusable beyond a few dozen digits.
• Fermat's little theorem: a^(p-1) ≡ 1 (mod p) — checkable without factoring.
• Its converse is false: pseudoprimes and Carmichael numbers.
• Miller-Rabin is probabilistic: error < 4^(-k), negligible from 40 bases on.
• Building and testing are easy, factoring is out of reach: the basis of RSA.
• This hardness is conjectural, and Shor's algorithm would remove it on a quantum machine.