Why everybody thinks AKS primarity test is a great thing? 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?
 A: 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)

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.
