Division with remainder using Newton iteration

Algorithm 3  

mathend000#

Theorem 3   Let R mathend000# be a commutative ring with identity element. Let a mathend000# and b mathend000# be univariate polynomials over R mathend000# with respective degrees n mathend000# and m mathend000# such that n $\geq$ m $\geq$ 0 mathend000# and b $\neq$ 0 mathend000# monic. Algorithm 3 computes the quotient and the remainder of a mathend000# w.r.t. b mathend000# in 4 $\bf M$(n - m) + $\bf M$(max(n - m, m)) + $\cal {O}$(n) mathend000# operations in R mathend000#

Proof. Indeed, Algorithm 3 consists essentially in

• 3 mathend000# multiplications in degree n - m + 1 mathend000#, plus operations in O(n - m + 1) mathend000# operations in R mathend000#, in order to compute g mathend000# (by virtue of Theorem 1),
• one multiplication in degree n - m + 1 mathend000# to compute q mathend000#,
• one multiplication in degree max(n - m, n) mathend000#, and one subtraction in degree n mathend000# to compute r mathend000#.

$\qedsymbol$

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

Remark 8   In Theorem 3, the complexity estimate becomes 3 $\bf M$(n - m) + $\bf M$(max(n - m, n)) + $\cal {O}$(n) mathend000# if the middle product technique described in Remark 6 applies. Moreover, if n - m $\leq$ n mathend000# holds, the $\cal {O}$(n) mathend000# can be repalced by $\cal {O}$(m) mathend000#.