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?


  • 2
    $\begingroup$ Compared to probabilistic algorithms AKS is horribly inefficient. $\endgroup$ – Maeher Jul 15 '13 at 7:16
  • $\begingroup$ Because asymptotic complexity isn't the whole story. $\endgroup$ – Thomas Jul 15 '13 at 7:17
  • $\begingroup$ Thanks Maeher and Thomas, could you please clarify the answer in a bit more details? Thanks $\endgroup$ – Faith Jul 15 '13 at 7:20
  • 2
    $\begingroup$ 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. $\endgroup$ – CodesInChaos Jul 15 '13 at 10:35
  • $\begingroup$ @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. $\endgroup$ – 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

  • 4
    $\begingroup$ It'd be useful to add a column that states the probability of being wrong. $\endgroup$ – CodesInChaos Jul 15 '13 at 9:54
  • $\begingroup$ I wonder how this Las Vegas algorithm would compare to ECPP. $\:$ $\endgroup$ – user991 Jul 15 '13 at 20:25
  • $\begingroup$ To clarify this table (what does the middle column mean): AKS and ECPP are deterministic, while Rabin Miller is probabilistic so it requires a "numer of trials" input. ECPP is (practically/empirically) the fastest of the two deterministic algos, but (probabilistic) Rabin-Miller is still very widely used in crypto because it is so simple/fast and you can increase the number of trials as much as you want to be confident in the test result. $\endgroup$ – arielf Jul 14 '17 at 23:23
  • $\begingroup$ @CodesInChaos The probabilities of a false negative are $4^{-1}$, $4^{-10}$, $4^{-100}$, $0$, and $0$, respectively. $\endgroup$ – forest May 16 '18 at 5:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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