why AKS is so slow in practice? [closed]

Question

This note (http://maths-people.anu.edu.au/~brent/pd/primality4.pdf) states that AKS is not practical. However, it is known that AKS runs in polynomial-time, and I cannot understand where the slowness of AKS algorithm comes from? Brent, on the above link, justifies this to the high probability of hardware errors during the computation of the algorithm? can some one, either explain Bret's justification, or explain me other drawbacks?

Answer 1

Here is the issue about hardware errors that Brent is worried about on the slides (I'm not saying I agree; I just saying what the issue is):

Suppose we ran our algorithm, and it gave a result "it's prime"; how can we be certain that the algorithm didn't gave us the wrong answer because of an internal hardware error while running the algorithm? This may sound like a trivial point, as the error probability on real hardware is actually quite small. However the entire reason we're not running 100 iterations of Miller-Rabin is that we want to be certain; are we as certain we didn't run into an internal error within AKS as we would be that 100 iterations of Miller Rabin (which is a lot faster than AKS for any reasonable input size) didn't all lie?

Well, AKS just outputs an answer "Prime" or "Not Prime"; if you want to verify the result, we have no better way than to run AKS again.

In contrast, consider the alternative algorithm Elliptic Curve Primality Proving or ECPP. This algorithm also always answers "Prime" or "Not Prime", and is always correct. However, it also generates a "Primality Certificate"; this primality certificate can be rechecked with a separate fast algorithm. No such primality certificate exists for a composite number; hence once we've run ECPP (and have generated a certificate), it is less important if we hit a hardware error during ECPP; if the primality certificate verifies, the number must be prime (even if ECPP did get a hardware error).

The above is the answer to the question; here is another point to consider.

ECPP is, in practice, considerably faster than AKS. Hence, unless someone finds a further advance in AKS (and reduces its exponent), there's little reason to actually use AKS in practice; if you insist on a provable prime, you use ECPP; if probabilistic methods are good enough, you use Miller-Rabin (or similar algorithms); alternatively, if what you're doing is searching for prime numbers, you can consider provable methods of constructing prime numbers (such as Shawe-Taylor).

So, if AKS is not useful in practice, why are people so interested in it? Well, while ECPP is faster, it's actually a Las Vegas algorithm; it's randomized, however, unlike Miller-Rabin, it'll never return an incorrect answer; instead, its low probability failure mode is that it might continue to run. In contrast, AKS is a deterministic polynomial time algorithm.