Next: Hensel Lifting Up: Division with remainder using Newton Previous: Modular inverses using Newton iteration

## Division with remainder using Newton iteration

Algorithm 7

Theorem 11   Let R be a commutative ring with unity. Let a and b be univariate polynomials over R with respective degrees n and m such that n m 0 and b 0 monic. Algorithm 7 computes the quotient and the remainder of a w.r.t. b in (n - m) + (m) + (m) operations in R

Proof. We do not give here a proof and we refer to Theorem 9.5 in [vzGG99]. However, roughly speaking, Algorithm 7 consists essentially in
• c multiplications (where c is a constant) to compute g (by virtue of Theorem 9),
• one multiplication to compute q,
• one multiplication to compute r.

Remark 15   If several divisions by a given b needs to be performed then we may precompute the inverse of revm(b) modulo some powers x, x2,... of x. Assuming that R possesses suitable primitive roots of unity ee can also save their DTF.

Next: Hensel Lifting Up: Division with remainder using Newton Previous: Modular inverses using Newton iteration
Marc Moreno Maza
2003-06-06