## Elements of correction

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

 (10)

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:

 (12)

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 .
To summarize the key ideas for this exercise are:
• 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.

Marc Moreno Maza
2008-03-18