Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I noticed that non-deterministic primality testing algorithms are more commonly used in practice while there is a deterministic algorithm e.g., AKS which runs in polynomial time? I am right? if so, then why? is there any drawbacks of using AKS?


share|improve this question
Compared to probabilistic algorithms AKS is horribly inefficient. – Maeher Jul 15 '13 at 7:16
Because asymptotic complexity isn't the whole story. – Thomas Jul 15 '13 at 7:17
Thanks Maeher and Thomas, could you please clarify the answer in a bit more details? Thanks – Faith Jul 15 '13 at 7:20
On real hardware all algorithms are probabilistic and something like $2^{-200}$ is certainly smaller than the probability of your hardware messing up the computation. So deterministic algorithms don't really offer a practical advantage. – CodesInChaos Jul 15 '13 at 10:35
@CodesInChaos This argument in general is true if and only if an attacker cannot control the inputs to the algorithm (e.g. in an attempt to make it fail), fortunately most modern primality tests (including Rabin-Miller) are immune to this to an arbitrary number of rounds. – Thomas Jul 16 '13 at 5:47

The simple answer is that AKS horribly inefficient in the real world. Even the asymptotic complexity is orders of magnitudes higher than the one of probabilistic algorithms. Here is a comparison of AKS with Rabin-Miller and other probabilistic algorithms. The following table illustrates the problem nicely (The tested number was $10^{ 100} + 267$:

runtime of primality tests

share|improve this answer
It'd be useful to add a column that states the probability of being wrong. – CodesInChaos Jul 15 '13 at 9:54
I wonder how this Las Vegas algorithm would compare to ECPP. $\:$ – Ricky Demer Jul 15 '13 at 20:25

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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