Four small primes, one big promise: deterministic Miller–Rabin for 32‑bit integers

The short version

It has been reported that running Miller–Rabin with just the bases 2, 3, 5 and 7 yields a deterministic primality test for every 32‑bit integer. Fast, simple, and pleasantly surprising — four tiny bases do the heavy lifting that a randomized test normally leaves to chance. Who knew you could make probabilistic math behave so well with a handful of primes?

A little background (because context matters)

Miller–Rabin started life as a randomized, tunable check: run more bases, shrink the chance of a false positive. Over the decades that followed, researchers have tightened the screws — both randomized and deterministic approaches have improved, culminating in AKS (a condition‑free deterministic polynomial‑time method) and pragmatic hybrids like Baillie‑PSW that practitioners still favor. Strong pseudoprimes lurk at the heart of the problem: composites that masquerade as primes for a given base. The OEIS sequence A014233 catalogs those tricky numbers, and that data is what underpins the four‑base rule for 32‑bit inputs.

The real-world angle

Jeremy Kun, working on homomorphic encryption needs, dug through that literature and code, and published a clear C++ implementation that uses the bases {2,3,5,7} plus the usual exponentiation and n−1 = d·2^s decomposition to make the Miller–Rabin check deterministic for 32‑bit values. It’s an elegant, pragmatic win: instead of relying on randomness or heavyweight algebra, you get a tiny routine that’s fast, auditable, and more than adequate for many engineering tasks — generating lists of 32‑bit primes, sanity checks in crypto libraries, or embedded systems with tight resource budgets.

So what now?

This isn’t a bombshell that overturns number theory. But it’s a nice reminder that careful empirical study — Pomerance, Selfridge, Wagstaff and others did the heavy lifting here — can turn a probabilistic tool into a deterministic one for useful domains. There’s a bit of sport around picking optimal base sets (the SPRP bases community keeps score), and the larger story — how to balance speed, simplicity, and adversarial robustness in primality testing — is very much alive. Practical takeaway? If you’re only dealing with 32‑bit ints, test 2, 3, 5 and 7 and sleep easier.

Sources: jeremykun.com, Hacker News