Gary L. Miller

Gary Lee Miller (born 1947) is an American computer scientist whose name every programmer meets the first time they need a fast primality test. His 1976 work turned the ancient question "is this number prime?" into a problem of modern computational complexity — and tied it, beautifully and unexpectedly, to one of the deepest open problems in mathematics, the Generalised Riemann Hypothesis.

Miller's test — primality meets the GRH

In his PhD work Miller devised a deterministic test for primality based on the structure of the multiplicative group modulo n. He proved it runs in polynomial time — but only conditionally: the argument needs a bound on the smallest number that witnesses a composite, and that bound follows if the Generalised Riemann Hypothesis holds. So Miller had shown something striking: if a famous conjecture about the zeros of Dirichlet L-functions is true, then primality testing is in \mathrm{P}. It was a vivid demonstration that analytic number theory and the theory of algorithms are the same subject wearing different clothes.

Rabin's twist, and a test used everywhere

A year later Michael Rabin removed the dependence on an unproven hypothesis by making the test randomised: instead of checking the specific witnesses GRH would guarantee, pick witnesses at random. A composite number is caught by at least three-quarters of possible witnesses, so a handful of random trials makes the error probability vanishingly small. The result is the Miller–Rabin primality test — fast, simple, and the workhorse behind the key generation in nearly every cryptographic library in the world. Miller's deterministic insight and Rabin's randomisation together made industrial-strength primality practical.

Yes — and it is one of the great stories of theoretical computer science. In 2002 three Indian researchers, Manindra Agrawal, Neeraj Kayal and Nitin Saxena, produced the AKS primality test: a fully deterministic, unconditional polynomial-time algorithm, settling the question Miller had left hanging on the GRH. Remarkably, two of the authors were undergraduates. AKS is a landmark of pure theory — though in practice Miller–Rabin remains the test everyone actually runs, because it is far faster. Miller's conditional result had shown the target was reachable; it took a quarter-century to hit it without assumptions.

Beyond primes

Miller's career ranged far past that one theorem. He has been a leader in the design of parallel and graph algorithms — notably spectral and geometric methods for partitioning meshes, and fast solvers for systems arising from graphs — work that earned him the Knuth Prize in 2013 for lifetime achievement in the foundations of computer science. A long-time professor at Carnegie Mellon, he is one of those researchers whose fingerprints are on tools used daily by people who have never heard his name.