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