Can somebody explain why AKS test is good?

As I understand AKS, a number $p$ is prime, if all coefficients of the polynomial $(x+a)^p$, except first and last, are multipe of $p$.

It seems the test takes very long time to execute. Look, number of coefficients is O(p) and, for large numbers, validation if a number is $p$'s multiple takes ln(p). So, total is O(p* ln(p)).

The naive primarity test (try to divide $p$ by all numbers up to square root of $p$), takes the same time.

Am I missing something?

  • 3
    $\begingroup$ The AKS primality test is a little cleverer than what you describe, even though it relies on the same concept. So, it runs in $\tilde{O}(\log(p)^{12})$ time, which is faster than the naive test. "In other words, the algorithm takes less time than the twelfth power of the number of digits in n times a polylogarithmic (in the number of digits) factor." $\endgroup$
    – B. Mehta
    May 27 '17 at 21:44
  • 2
    $\begingroup$ article by Granville for the a.m.s. bulletin, much easier to read than the original paper www2.math.uu.se/~vera/undervisning/komplexitetsteori/… $\endgroup$
    – Will Jagy
    May 27 '17 at 21:48
  • $\begingroup$ What is a "multiplier" of $p$? Is that a typo for "multiple"? $\endgroup$
    – bof
    May 28 '17 at 1:00
  • 1
    $\begingroup$ @WillJagy Thanks so much for that paper link! $\endgroup$
    – Ben
    May 29 '17 at 3:58

The AKS test is more complicated than what you describe, which was known in the 1600s and known to be exponential time. Indeed, what you describe is worse than the most naive trial division. Unfortunately the numberphile video has made lots of people think this is the AKS test.

If you look at a graph of times taken for some primality test implementations, on a log-log scale, you can see AKS (the real thing) has nice straight lines, showing it is polynomial in the size of the input, and it turns out all three implementations have exponents of about 6, which is expected. You can also see that it is more efficient than trial division after the input is large enough (the particular trial division method skipping multiples of 2/3/5/7). Using all of the collected improvements Bernstein published, the crossover point is actually not that large (~16 digits for these implementations)

Primality proof times

As expected, trial division is exponential in the size of the input. AKS is polynomial, and APR-CL and ECPP are practically a lot faster than either, with smaller exponents as well.

The AKS test was very important for the theory, and is extremely clever. It has not yet led to practical use better than our other methods. As Will Jagy points out, Granville's paper is a great resource for understanding the history, the algorithm, and the significance.

  • $\begingroup$ Just curious, what is the (original) source of that graph? $\endgroup$
    – dxiv
    May 28 '17 at 5:03
  • $\begingroup$ A .ods spreadsheet, using a slightly modified standalone ecpp-dj (which has support for everything except Primo's ECPP), run on a i7-4770k / 4.3GHz. $\endgroup$
    – DanaJ
    May 29 '17 at 0:13
  • $\begingroup$ Curiosity satisfied, thank you. $\endgroup$
    – dxiv
    May 29 '17 at 0:53
  • $\begingroup$ I do not see how algorythm can be exponential. It seems to be polinomeal. $\endgroup$
    – polina-c
    May 29 '17 at 2:43
  • 1
    $\begingroup$ @PolinaC you are confusing the input 'n' with the SIZE of the input, 'log(n)'. Primality using trial division, e.g. finding one factor, is exponential in the size of the input. $\endgroup$
    – DanaJ
    Jun 2 '17 at 23:58

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.