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 $\geq$ m $\geq$ 0 and b $\neq$ 0 monic. Algorithm 7 computes the quotient and the remainder of a w.r.t. b in 4 $\bf M$(n - m) + $\bf M$(m) + $\cal {O}$(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.

$\qedsymbol$

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