# Coefficients growth in the Euclidean Algorithm over

We saw in the first chapter that running the Euclidean Algorithm in can lead to a significant expression swell. Let us try to estimate how coefficients grow. That is, we want to estimate the maximal space needed to store one coefficient of an intermediate polynomial. Let be the number of bits of a machine word.

Definition 1   For an integer we define the length of as the minimum number of words to encode . Hence for we have

 (1)

For a rational number with and we define , the length of , as the maximum among and .

Definition 2   For a polynomial of degree such that all coefficients have denominator and such that the numerators have gcd 1 then we define the length of as

 (2)

Remark 1   A polynomial of degree can be represented with

 (3)

words.

Proposition 1   Let be univariate polynomials over in . Then we have
1. .
2. .

Proof. See [GG99].

Proposition 2   Let be univariate polynomials over in . We assume that and are monic and that holds. Let and be the quotient and the remainder of w.r.t. . Then we have

 (4)

Proof. We define

 (5)

It is not hard to see that

 (6)

Then

 (7)

Thus

 (8)

Recall that

 (9)

Since we obtain

 (10)

Indeed and .

Remark 2   A similar result as Proposition 2 holds for monic polynomials such that . See [GG99]. These results provide us with an exponential upper bound for the coefficient of the gcd computed by the Euclidean Algorithm. But in fact a polynomial bound can be established. Moreover there is an efficient modular approach for computing gcds in and as we shall see in the next sections.

Marc Moreno Maza
2008-01-07