I saw Carl Pomerance yesterday give a wonderful presentation on the AKS primality algorithm. He made an interesting point about the algorithm. The algorithm runs in time O(n¹²) where n is the number of bits of the input to be tested. The big O notation hides a constant, i.e., the algorithm uses c n¹² for some constant c. That c is unknown!

The AKS algorithm uses a result by Fouvry on the distribution of certain kinds of primes. Fouvry's result uses another result that is proven as such: First it is proved assuming the Extended Riemann Hypothesis is true. If the ERH fails, then the place where it fails can be used to prove the result. The constant c will depend on where the ERH fails. To determine c would require settling the Extended Riemann Hypothesis!

Agrawal, Saxena and Kayal did not cheat; they really gave a polynomial-time algorithm for primality. Their algorithm is fixed, only the analysis of the running time is affected by the ERH. Also there are other results one can use instead of Fouvry that get around this issue. Still I find it neat that this algorithm that gives a provably polynomial-time algorithm for primality has a running time that, while polynomial, is completely unknown.