## Division with remainder using Newton iteration

Algorithm 3

Theorem 3   Let be a commutative ring with identity element. Let and be univariate polynomials over with respective degrees and such that and monic. Algorithm 3 computes the quotient and the remainder of w.r.t. in operations in

Proof. Indeed, Algorithm 3 consists essentially in
• multiplications in degree , plus operations in operations in , in order to compute (by virtue of Theorem 1),
• one multiplication in degree to compute ,
• one multiplication in degree , and one subtraction in degree to compute .

Remark 7   If several divisions by a given needs to be performed then we may precompute the inverse of modulo some powers of . Assuming that possesses suitable primitive roots of unity, we can also save their DTF.

Remark 8   In Theorem 3, the complexity estimate becomes if the middle product technique described in Remark 6 applies. Moreover, if holds, the can be repalced by .

Marc Moreno Maza
2008-01-07