How does the AKS algorithm work?

Question

I looked at the article of AKS in wikipedia (https://en.wikipedia.org/wiki/AKS_primality_test) and I don't understand how can I do the last level in a polynomial time (relatively to the number of digits of $n$). I need to check if there are polynomials $f(x),g(x)$ so that $(x+a)^n-(x^n+a)=nf(x)+(x^r-1)g(x)$.

How can I do that in a polynomial time? Calculating the coefficients of $(x+a)^n-(x^n+a)$ using the binomial theorem takes an exponential time and even if I can check if $(x+a)^n-(x^n+a)=nf(x)+(x^r-1)g(x)$ in a polynomial time, I still need to check this for every $f(x),g(x)$, which is at least exponential time.

Is there a trick or something that lets me do it in a shorter time?

Thanks for answering

Answer 1

If $u(x)$ is a polynomial over $\Bbb Z$ there is a unique polynomial $v(x)$ such that $$u(x)\equiv v(x)\mod{\left<n,x^r-1\right>}$$ and where $\deg v<r$ and the coefficients of $v$ lie in $\{0,1,\ldots,n-1\}$. Call finding $v(x)$ given $u(x)$ reducing $u(x)$ modulo $\left<n,x^r-1\right>$.

So we have to reduce $(x+a)^n-x^n-a$ modulo $\left<n,x^r-1\right>$ and determine if that is zero. The hard part is reducing $(x+a)^n$ modulo $\left<n,x^r-1\right>$. One can do that in polynomial time by adapting the exponentiation by squaring method. This requires $O(\log n)$ iterations, and each stage required reducing a polynomial of degree $<2n$ and with coefficients of size $O(nr)$ modulo $\left<n,x^r-1\right>$.