- Define:
(1)

The following discussion is meant to give upper bounds for the quotient and the remainder in the division-with-remainder of by . We follow the classical algorithm (not the fast one) as stated at the beginning of the chapter on fast division.Observe that the quotient has degree , so we define:

(2)

Since is monic, we clearly have:(3)

Let be the ``initial'' remainder and let be the largest absolute value of a coefficient in . During the first iteration is replaced by(4)

The ``intermediate'' remainder is either null or the largest absolute value of a coefficient in satisfies:(5)

If , then the next intermediate remainder satisfies(6)

where is the leading coefficient of and, also, the next non-zero coefficient in . If , then the largest absolute value of a coefficient in satisfies:(7)

Then, an easy induction leads to:(8)

Observe that an upper bound for the absolute value of a coefficient in is rather(9)

- We make a preliminary observation.
Let
be an odd integer such that we have

Note that this implies(11)

We represent the elements of with the symmetric range . Let be the corresponding canonical ring homomorphism from to . In we have:

This implies the following in :(13)

Observe that we have:(14)

**We shall describe now**how to compute and , and thus and .Consider odd primes such that their product satisfies (10). For all , let , , and be the respective images of , , and in . Thus, for all , we have in

(15)

By virtue of the uniqueness of the division by a monic polynomial, this implies that for all , the couple is the couple quotient-remainder in the division of by . Applying coefficient-wise the Chinese Remaindering Algorithm (see course notes) we construct polynomials , , and in such that(16)

Moreover, the Chinese Remaindering Theorem tells us that we have:(17)

Using the preliminary remark, we conclude that and . This approach is interesting when fast division is available in each .

- is an upper bound for (the absolute value of a coefficient in) the quotient
- for designing a modular method that reconstruct both
and
we can use the bound
;
alternatively, we can
- reconstruct the quotient only and then use the smaller bound ,
- then, get as .

- the modular reconstruction relies on
- the correct choice of the product of the primes, which must be greater than twice the bound,
- the Chinese Remaindering Theorem and Algorithm,
- the uniqueness of the division-with-remainder by a monic polynomial.

*
*

2008-03-18