I'm trying to learn about Agrawal–Kayal–Saxena (AKS for short) primality test but I have some trouble understanding its efficiency.

If I understood correctly, the test amounts to probing whether the entries of $n$-th row of Pascal's triangle divide $n$. There are $n/2$ (because of the symmetry) entries and all are larger than $n$.

Trial divison tries to divide $n$ with all the (odd) numbers below $\sqrt{n}$.

What I don't understand is how could AKS by possibly (asymptotically) faster, as it tests more and larger numbers?

That's leaves me with the assumption that the above description of AKS is horribly inefficient. If that is the case, is it possible to explain in simple terms some strategies for improving the performance?

  • $\begingroup$ Please, recall what AKS is (it's far from being a common acronym) or at least give a reference. $\endgroup$
    – Jean Marie
    Dec 8 '17 at 20:49
  • $\begingroup$ @JeanMarie Sorry, done! $\endgroup$
    – Hinrik
    Dec 8 '17 at 20:51
  • $\begingroup$ Wikipedia has a "horribly inefficient" description? A very common situation. mathworld.wolfram.com/AKSPrimalityTest.html gives a better explanation. $\endgroup$
    – Mr. Brooks
    Dec 9 '17 at 22:42
  • 1
    $\begingroup$ @Mr.Brooks, I think you're assumed this came from Wikipedia, which it did not. Wikipedia's page shows what was described, indicates that it is terribly inefficient, and then shows how AKS is derived from this. Just like the paper. The proper v6 algorithm is shown on the page. My opinion is that MathWorld's page is much less informative (mostly because it's really short and assume the reader will read the references to actually figure anything out). $\endgroup$
    – DanaJ
    Dec 10 '17 at 1:52

The explanation you give is describing Lemma 2.1 in the AKS paper (equation 1 in the concepts of the Wikipedia entry). This was known in the 1600's and is exponential time. It is inefficient even compared to naive trial division.

The popular Numberphile video can be easily inferred to state that this, known computationally inefficient method, is the AKS primality test. It is not. The very clever trick in AKS is reducing both the number of entries and their size, and proving that they can be reduced sufficiently such that the test is polynomial in the size of the input.

The Wikipedia page algorithm summarizes the method, and there are some worked examples. This should be sufficient to get started, though testing the polynomials should be done with sufficient optimizations as that's where all the time is spent.

In my experience, trial division is still faster until something like $10^{17}$ or so, after which AKS is faster. The exact crossover will depend on your implementations. That crossover used a significant Bernstein theorem 4.1 improvement, while the algorithm from the v6 paper (as on Wikipedia) crosses over at about $10^{25}$. I'm sure the trial division method could be optimized some more.

There's also not any practical point other than the intellectual challenge. The BPSW test is general, polynomial, deterministic, and unconditional for all 64-bit inputs (i.e. smaller than 18,446,744,073,709,551,616). It is thousands to millions of times faster than AKS. Past that number, we find the APR-CL and ECPP tests to be substantially faster and with small exponents. They are also unconditionally correct and not probabilistic tests. There are some neat things about AKS that make it attractive for stating computational complexity, and it is mathematically fascinating. But it isn't actually used in practice.

  • $\begingroup$ Thank you very much for the thorough answer! And sorry, I don't have enough reputation to upvote! $\endgroup$
    – Hinrik
    Dec 9 '17 at 6:48
  • $\begingroup$ Nice answer (+1) $\endgroup$
    – Peter
    Dec 9 '17 at 10:16

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.