# Primality testing (deterministic vs. non-deterministic)

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?

Thanks,

• Compared to probabilistic algorithms AKS is horribly inefficient. Commented Jul 15, 2013 at 7:16
• Because asymptotic complexity isn't the whole story. Commented Jul 15, 2013 at 7:17
• Thanks Maeher and Thomas, could you please clarify the answer in a bit more details? Thanks Commented Jul 15, 2013 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. Commented Jul 15, 2013 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. Commented Jul 16, 2013 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$:
• I wonder how this Las Vegas algorithm would compare to ECPP. $\:$
• @CodesInChaos The probabilities of a false negative are $4^{-1}$, $4^{-10}$, $4^{-100}$, $0$, and $0$, respectively. Commented May 16, 2018 at 5:45