Next: The quotient as a modular Up: Division with remainder using Newton Previous: Division with remainder using Newton

## Classical division with remainder

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

Algorithm 5

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

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

Remark 10   One can derive from Algorithm 5 a bound for the coefficients of q and r, which is needed for performing a modular version (based for instance on the CRT). Let | | a | |, | | b | | and | | r | | be the max-norm of a, b and r. Let | bm | be the absolute value (over ) or the norm (over ) of the leading coefficient of b. Then we have

 | | r | |     | | a | | 1 + (64)

Next: The quotient as a modular Up: Division with remainder using Newton Previous: Division with remainder using Newton
Marc Moreno Maza
2003-06-06