# AKS primality test vs. trial division performance

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?

• Please, recall what AKS is (it's far from being a common acronym) or at least give a reference. Dec 8 '17 at 20:49
• @JeanMarie Sorry, done! Dec 8 '17 at 20:51
• Wikipedia has a "horribly inefficient" description? A very common situation. mathworld.wolfram.com/AKSPrimalityTest.html gives a better explanation. Dec 9 '17 at 22:42
• @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). Dec 10 '17 at 1:52

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.