Note on fast division algorithm for polynomials using Newton iteration

Abstract

The classical division algorithm for polynomials requires $O(n^2)$ operations for inputs of size $n$. Using reversal technique and Newton iteration, it can be improved to $O(M(n))$, where $M$ is a multiplication time. But the method requires that the degree of the modulo, $x^l$, should be the power of 2. If $l$ is not a power of 2 and $f(0)=1$, Gathen and Gerhard suggest to compute the inverse,$f^{-1}$, modulo $x^{\lceil l/2^r\rceil },x^{\lceil l/2^{r-1}\rceil },...,x^{\lceil l/2\rceil },x^l$, separately. But they did not specify the iterative step. In this note, we show that the original Newton iteration formula can be directly used to compute $f^{-1}mod{x}^l$ without any additional cost, when $l$ is not a power of 2.

arXiv comment5 pages