This post continues my series on favorite theorems of the twenty-first century. For an overview of the categories and my earlier selections, see this post.
My choice for 2003 in Algorithms and Complexity is the theorem of Agrawal, Kayal, and Saxena establishing the existence of a deterministic polynomial-time algorithm for deciding whether a given integer is prime or composite. Their work was published in 2004 (Agrawal et al. 2004).
One of the fundamental algorithmic problems in number theory is primality testing: given an integer , determine whether is prime or composite. The most direct approach is to test every possible divisor between and . This requires on the order of divisions and is therefore exponential in the number of digits of . The natural question is whether primality can be decided much more efficiently.
Primality testing is a decision problem: a yes-or-no question defined on an infinite collection of finite inputs. A decision problem belongs to the complexity class if there is an algorithm that always returns the correct answer and whose running time is bounded by a polynomial in the length of the input. Since an integer can be represented using bits, a polynomial-time primality test must run in bit operations for some constant .
In 1976, Miller (Miller 1976) gave a polynomial-time primality test whose correctness depends on the Extended Riemann Hypothesis. In 1980, Rabin (Rabin 1980) converted Miller’s method into an unconditional randomized algorithm. The resulting Miller–Rabin test runs in polynomial time and can make its probability of error arbitrarily small. It is extremely effective in practice, but it does not by itself show that primality testing belongs to , since an algorithm in must be deterministic and always correct.
A major deterministic advance came in 1983, when Adleman, Pomerance, and Rumely (Adleman et al. 1983) constructed a primality test with running time This is only slightly worse than polynomial time, but it is not polynomial. Agrawal, Kayal, and Saxena finally closed the gap by constructing a deterministic algorithm with running time polynomial in .
The starting point of the proof is an elementary consequence of the binomial theorem. If is prime, then every intermediate binomial coefficient is divisible by . Consequently, for every integer , Equivalently, This polynomial identity can be made computationally useful by also reducing modulo . Thus, if is prime, then for every pair of positive integers and , In explicit divisibility form, condition says that there exist polynomials such that
Testing the corresponding identity without reducing modulo would be impractical, since the polynomial has degree . Reduction modulo replaces it by a polynomial of degree less than . The central achievement of Agrawal, Kayal, and Saxena was to show that can be chosen deterministically and bounded by a polynomial in . They also showed that it is enough to test the congruence for only polynomially many values of .
With suitable elementary preliminary checks, these congruences have a powerful converse: if the required identities hold, then must be a prime power. Since perfect powers can themselves be recognized deterministically in polynomial time, one can distinguish primes from composite prime powers without sacrificing the polynomial running-time bound. Every step of the resulting algorithm is deterministic, and the total number of bit operations is bounded by a polynomial in . This proves Theorem and establishes that primality testing belongs to .