Algorithms and Parallel Computing

18.2 THE POLYNOMIAL DIVISION ALGORITHM

Assume that the dividend polynomial A of degree n is given by

(18.1)

The divisor polynomial of degree m is given by

(18.2)

The polynomial division operation produces the quotient and remainder polynomials Q and R

(18.3)

(18.4)

where

(18.5)

The division operation is a series of multiply/subtract iterations such that after each iteration one coefficient of the quotient polynomial is obtained, in descending order. Also, a partial remainder polynomial having m terms is obtained after each iteration. At the end of the iterations, all the coefficients of Q are determined as well as the final remainder polynomial R.

The notation we use in this chapter for the partial remainder polynomials is as follows:

• R(i): input partial remainder polynomial at iteration i
• R(i + 1): resulting partial remainder polynomial at iteration i
• r_j(i): jth coefficient of R(i), 0 ≤ j < m

According to the above definitions, can express R(i) explicitly as

(18.6) ...