Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question

closed as off-topic by orlp, Thomas, e-sushi, minar, D.W. Aug 9 '13 at 19:13

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions on mathematics are off-topic unless they relate directly to cryptography. These questions can usually be asked on Mathematics Stack Exchange." – orlp, Thomas, e-sushi, minar
If this question can be reworded to fit the rules in the help center, please edit the question.

4  
This question has nothing to do with cryptography. –  orlp Aug 9 '13 at 6:19
3  
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. –  Thomas Aug 9 '13 at 6:33
1  
@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 Aug 9 '13 at 12:05
2  
@nightcracker While primality testing isn't cryptography per-se, it's close enough for me to consider it on-topic here. –  CodesInChaos Aug 9 '13 at 12:28
2  
@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 Aug 9 '13 at 12:49

1 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.

share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.