On Fast Division Algorithm for Polynomials Using Newton Iteration

摘要

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~([l/2~r]), x~([l/2~(r-1)]) ,..., x~([l/2]), x~l, separately. But they did not specify the iterative step. In this paper, 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.