The Agrawal-Kayal-Saxena (AKS) primality test, discovered in 2002, is the first provably deterministic algorithm to determine the primality of a given number with a run time which is guaranteed to be polynomial in the number of digits, thus, given a large number , the algorithm will correctly determine whether that number is prime or not in time . (Many previous primality testing algorithms existed, but they were either probabilistic in nature, had a running time slower than polynomial, or the correctness could not be guaranteed without additional hypotheses such as GRH.)
The AKS test is of some relevance to the polymath project “Finding primes“, so I thought I would sketch the details of the test (and the proof that it works) here. (Of course, full details can be found in the original paper, which is nine pages in length and almost entirely elementary in nature.) It relies on polynomial identities that are true modulo when is prime, but cannot hold for non-prime as they would generate a large number of additional polynomial identities, eventually violating the factor theorem (which asserts that a polynomial identity of degree at most can be obeyed by at most values of the unknown).
Our starting point is Fermat’s little theorem, which asserts that
for every prime and every . This theorem suggests an obvious primality test: to test whether a number is prime, pick a few values of and see whether . (Note that can be computed in time for any fixed by expressing in binary, and repeatedly squaring .) If the statement fails for some , then would be composite. Unfortunately, the converse is not true: there exist non-prime numbers , known as Carmichael numbers, for which for all coprime to ( is the first example). So Fermat’s little theorem cannot be used, by itself, to establish primality for general , because it is too weak to eliminate all non-prime numbers. (The situation improves though for more special types of , such as Mersenne numbers; see my earlier post on the Lucas-Lehmer test for more discussion.)
However, there is a stronger version of Fermat’s little theorem which does eliminate all non-prime numbers. Specifically, if is prime and is arbitrary, then one has the polynomial identity
where is an indeterminate variable. (More formally, we have the identity in the ring of polynomials of one variable over the finite field of elements.) This identity (a manifestation of the Frobenius endomorphism) clearly implies (1) by setting ; conversely, one can easily deduce (2) from (1) by expanding out using the binomial theorem and the observation that the binomial coefficients are divisible by for all . Conversely, if
(i.e. in ) for some coprime to , then by comparing coefficients using the binomial theorem we see that is divisible by for all . But if is divisible by some smaller prime , then by setting equal to the largest power of that divides , one sees that is not divisible by enough powers of to be divisible by , a contradiction. Thus one can use (3) (for a single value of coprime to ) to decide whether is prime or not.
Unfortunately, this algorithm, while deterministic, is not polynomial-time, because the polynomial has coefficients and will therefore take at least time to compute. However, one can speed up the process by descending to a quotient ring of , such as for some . Clearly, if the identity holds in , then it will also hold in , thus
The point of doing this is that (if is not too large) the left-hand side of (4) can now be computed quickly (again by expanding in binary and performing repeated squaring), because all polynomials can be reduced to be of degree less than , rather than being as large as . Indeed, if , then one can test (4) in time .
We are not done yet, because it could happen that (4) holds but (3) fails. But we have the following key theorem:
Theorem 1 (AKS theorem) Suppose that for all , (4) holds, and is coprime to . Then is either a prime, or a power of a prime.
Of course, coprimality of and can be quickly tested using the Euclidean algorithm, and if coprimality fails then is of course composite. Also, it is easy to quickly test for the property that is a power of an integer (just compute the roots for ), and such powers are clearly composite. From all this (and (2), one soon sees that theorem gives rise to a deterministic polynomial-time test for primality. One can optimise the powers of in the bounds for (as is done in the original paper), but we will not do so here to keep the exposition uncluttered.
Actually, we don’t need (4) satisfied for all that many exponents to make the theorem work; just one well-chosen will do. More precisely, we have
Theorem 2 (AKS theorem, key step) Let be coprime to , and such that has order greater than in the multiplicative group (i.e. the residues for are distinct). Suppose that for all , (4) holds, and is coprime to . Then is either a prime, or a power of a prime.
To find an with the above properties we have
Lemma 3 (Existence of good ) There exists coprime to , such that has order greater than in .
Proof: For each , the number has at most prime divisors (by the fundamental theorem of arithmetic). If one picks to be the first prime not equal to any of these prime divisors, one obtains the claim. (One can use a crude version of the prime number theorem to get the upper bound on .)
It is clear that Theorem 1 follows from Theorem 2 and Lemma 3, so it suffices now to prove Theorem 2.
Suppose for contradiction that Theorem 2 fails. Then is divisible by some smaller prime , but is not a power of . Since is coprime to all numbers of size we know that is not of polylogarithmic size, thus we may assume for any fixed . As is coprime to , we see that is not a multiple of (indeed, one should view as being much larger than ).
Let be a field extension of by a primitive root of unity , thus for some factor (in ) of the cyclotomic polynomial . From the hypothesis (4), we see that
in for all , where . Note that is coprime to every integer less than , and thus .
Meanwhile, from (2) one has
in for all such . The two equations give
Note that the power of a primitive root of unity is again a primitive root of unity (and conversely, every primitive root arises in this fashion) and hence we also have
in for all .
Inspired by this, we define a key concept: a positive integer is said to be introspective if one has
in for all , or equivalently if , where is the ring homomorphism that sends to .
We have just shown that are all introspective; is also trivially introspective. Furthermore, if and are introspective, it is not hard to see that is also introspective. Thus we in fact have a lot of introspective integers: any number of the form for is introspective.
It turns out in fact that it is not possible to create so many different introspective numbers, basically the presence of so many polynomial identities in the field would eventually violate the factor theorem. To see this, let be the multiplicative group generated by the quantities for . Observe that for all . We now show that this places incompatible lower and upper bounds on . We begin with the lower bound:
Proof: Let be a product of less than of the quantities (allowing repetitions), then lies in . Since , there are certainly at least ways to pick such a product. So to establish the proposition it suffices to show that all these products are distinct.
Suppose for contradiction that , where are different products of less than of the . Then, for every introspective , as well (note that ). In particular, this shows that are all roots of the polynomial . But this polynomial has degree less than , and the are distinct by hypothesis, and we obtain the desired contradiction by the factor theorem.
Proposition 5 (Upper bound on ) Suppose that there are exactly residue classes modulo of the form for . Then .
Proof: By the pigeonhole principle, we must have a collision
for some with . Setting and , we thus see that there are two distinct introspective numbers of size most which are equal modulo . (To ensure that are distinct, we use the hypothesis that is not a power of .) This implies that , and thus for all . But the polynomial has degree at most , and the claim now follows from the factor theorem.
Since has order greater than in , we see that the number of residue classes of the form is at least . But then , and so Propositions 4, 5 are incompatible.
Update, Aug 12: A thorough discussion of the AKS algorithm by Andrew Granville for Bull. Amer. Math. Soc. can be found here.