# why AKS is so slow in practice? [closed]

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?

• This question has nothing to do with cryptography.
– orlp
Commented Aug 9, 2013 at 6:19
• I think it runs in $O(n^6)$ which while polynomial, is still horribly slow for even reasonably sized inputs, say $n = 2048$ (bits). Being polynomial time isn't the whole story, consider an algorithm with running time $O(n^{10^{1000}})$, sure it's polynomial time but is it really of any use? I have no idea what hardware errors have to do with this. No algorithm is immune to hardware failure. Commented Aug 9, 2013 at 6:33
• @Thomas The author of the linked slides states that AKS suffers from a significant chance on a hardware error. I think that his reasoning is that AKS has a long CPU-intensive runtime and that it does not generate a certificate which is easily verifiable. But this is just a guess.
– orlp
Commented Aug 9, 2013 at 12:05
• @nightcracker While primality testing isn't cryptography per-se, it's close enough for me to consider it on-topic here. Commented Aug 9, 2013 at 12:28
• @CodesInChaos Primality testing in itself is somewhat related to cryptography, but the question "Why is primality test X so slow?" is not, in my opinion.
– orlp
Commented Aug 9, 2013 at 12:49

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.

• Wait ECPP is faster than AKS? Why is everyone talking about AKS all the time then :/ Commented Feb 16, 2016 at 9:02
• @David天宇Wong: because AKS is provably a polytime algorithm (complexity class P), while ECPP is a randomized polytime algorithm (complexity class RP). Hence, AKS is better theoretically (it's in an easier complexity class), even though ECPP is better (at least, faster; implementing it correctly is nasty) practically. Commented Feb 16, 2016 at 14:26