# How does the AKS algorithm work?

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?

• Both the polynomial exponent and degree are constrained by a modulo. You also only test for $s$ different $a$ values (the loop end in step 5 on the wiki page), and the paper shows $s$ and $r$ grow slow enough so the whole algorithm is polynomial time. Running some implementations over various sizes does show the result is polynomial time with an exponent of 6+epsilon, just as expected. That still makes it very slow compared to APR-CL or ECPP in practice. Jul 19, 2020 at 12:09
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}$$ and where $$\deg v and the coefficients of $$v$$ lie in $$\{0,1,\ldots,n-1\}$$. Call finding $$v(x)$$ given $$u(x)$$ reducing $$u(x)$$ modulo $$\left$$.
So we have to reduce $$(x+a)^n-x^n-a$$ modulo $$\left$$ and determine if that is zero. The hard part is reducing $$(x+a)^n$$ modulo $$\left$$. 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$$.