Classical division with remainder

We assume that R mathend000# is a commutative ring with identity element. We consider the classical algorithm for univariate polynomial division with remainder stated over R mathend000# instead of a field. However, Algorithm 1 is well defined because we assume that the leading coefficient of the polynomial b mathend000# is a unit.

Algorithm 1  

mathend000#

Proposition 1   Let a mathend000# and b mathend000# two univariate polynomials in R[x] mathend000# with respective degrees n mathend000# and m mathend000# such that n $\geq$ m $\geq$ 0 mathend000# and the leading coefficient of b mathend000# is a unit. Then there exist unique polynomials q mathend000# and r mathend000# such that a = bq + r mathend000# and deg r  <  m mathend000#. The polynomials q mathend000# and r mathend000# are called the quotient and the remainder of a mathend000# w.r.t. to b mathend000#. Algorithm 1 compute them in (2m + 1)(n - m + 1) $\in$ $\cal {O}$(n m) mathend000# operations in R mathend000#.

Proof. We leave to the reader the proof of the uniqueness of the quotient and the remainder of a mathend000# w.r.t. to b mathend000#. So we focus now on the complexity result Consider an iteration of the for loop where deg r = m + i mathend000# holds at the begining of the loop. Observe that r mathend000# and q_ixⁱb mathend000# have the same leading coefficient. Since deg b = m mathend000#, computing the reductum of q_ixⁱb mathend000# requires m mathend000# operations. Then subtracting the reductum of q_ixⁱb mathend000# to that of r mathend000# requires again m mathend000# operations. Hence each iteration of the for loop requires at most 2m + 1 mathend000# operations in R mathend000#, since we need also to count 1 mathend000# for the computation of q_i mathend000#. The number of for loops is n - m + 1 mathend000#. Therefore Algorithm 1 requires (2m + 1)(n - m + 1) mathend000#. $\qedsymbol$

Remark 1   One can derive from Algorithm 1 a bound for the coefficients of q mathend000# and r mathend000#, which is needed for performing a modular version (based for instance on the CRT). Let | | a | | mathend000#, | | b | | mathend000# and | | r | | mathend000# be the max-norm of a mathend000#, b mathend000# and r mathend000#. Let | b_m | mathend000# be the absolute value (over $\mbox{${\mathbb Z}$}$ mathend000#) or the norm (over $\mbox{${\mathbb C}$}$ mathend000#) of the leading coefficient of b mathend000#. Then we have

$$\leq \left(\vphantom{ 1 + \frac{{\mid}{\mid}b{\mid}{\mid}}{\mid b_m \mid} }\right. {\frac{{{\mid}{\mid}b{\mid}{\mid}}}{{\mid b_m \mid}}} \left.\vphantom{ 1 + \frac{{\mid}{\mid}b{\mid}{\mid}}{\mid b_m \mid} }\right)^{{n-m+1}}_{}$$ (1)