A Fast Polynomial Multiplication Using only Integers for AKS Algorithm

Question

I'm getting stuck at choosing a fast polynomial multiplication algorithm for the last step of the AKS primality test:

for j in range(1, 2*len(n)*floor(sqrt(r))+2):
 if (X+j)^n != X^n+j (mod X^r-1, n):
 return False

In the AKS paper, the authors assert that we can multiply two $r$-degree polynomials which contain coefficients at most $O(\log n)$ in $\tilde{O}(r\log n)$ time. I think we need both fast integer and polynomial multiplying algorithms to acquire the complexity $\tilde{O}(r\log n)$, rather than $O(r^2\log(n)^2)$ when applying only plain multiplying methods.

I wish to implement the AKS primality test, which uses only integers to operate. Moreover, I need fast multiplying methods to obtain the optimized complexity, i.e., $\tilde{O}(r\log(n))$ rather than $O(r^2\log(n)^2)$. Most fast polynomial multiplying algorithms I have known use real numbers, such as FFT, which may cause a false result when the input $n$ is large enough. Does there exist fast optimized polynomial multiplying algorithms taking advantage of only integers to compute? Is the plain multiplying method the only choice?

• Emil Jeřábek: There are many algorithms. And in particular, FFT-based algorithms that work over rings of integers modulo a large integer rather than real numbers. See en.wikipedia.org/wiki/Multiplication_algorithm .