4
$\begingroup$

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,

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

1 Answer 1

3
$\begingroup$

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

$\endgroup$
4
  • 4
    $\begingroup$ It'd be useful to add a column that states the probability of being wrong. $\endgroup$ Jul 15, 2013 at 9:54
  • $\begingroup$ I wonder how this Las Vegas algorithm would compare to ECPP. $\:$ $\endgroup$
    – user991
    Jul 15, 2013 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, 2017 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, 2018 at 5:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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