Next: Relation between gcds in [x] Up: Advanced Computer Algebra: The resultant Previous: Advanced Computer Algebra: The resultant

# Coefficients growth in the Euclidean Algorithm over [x]

We saw in the first chapter that running the Euclidean Algorithm in [x] 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 N be the number of bits of a machine word.

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

 (a) = log2(a)/N + 1    and    (0) = 0 (1)

For a rational number a = b/c with b, c and gcd(c, d )= 1 we define (a), the length of a, as the maximum among (b) and (c).

Definition 2   For a polynomial a [x] of degree n 0 such that all coefficients have denominator b and such that the numerators an, an-1,..., a1, a0 have gcd 1 then we define the length of a as

 (a) = max((b),((ai))) (2)

Remark 1   A polynomial a [x] of degree n 0 can be represented with

 (a)2 + deg(a) (3)

words.

Proposition 1   Let a, b be univariate polynomials over in x. Then we have
1. (a + b  max((a),(b)) + 1.
2. (ab  (a) + (b) + (min(deg(a), deg(b)) + 1).

Proof. See [vzGG99].

Proposition 2   Let a, b be univariate polynomials over in x. We assume that a and b are monic and that deg(a) = deg(b) + 1 holds. Let q and r be the quotient and the remainder of a w.r.t. b. Then we have

 (r)   (a) + 2(b) + 3 (4)

Proof. We define

 a  =  xn + an-1xn-1 + ... + a0    and    b  =  xn-1 + bn-2xn-2 + ... + b0 (5)

It is not hard to see that

 q  =  x + an-1 - bn-2 (6)

Then

 (q)   max((a),(b)) + 1 (7)

Thus

 (bq)   max((a),(b)) + 1 + (b) + (deg(q) + 1) (8)

Recall that

 r  =  a - bq (9)

Since (bq) (a) we obtain

 (r) max((a),(b)) + 1 + (b) + (deg(q) + 1) + 1 (a) + 2(b) + 3
(10)

Indeed max((a),(b))   (a) + (b) and (deg(q) + 1)  =  (2)   1.

Remark 2   A similar result as Proposition 2 holds for monic polynomials a, b [x] such that deg(a) = deg(b) + 1. See [vzGG99]. 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 [x] and [x] as we shall see in the next sections.

Next: Relation between gcds in [x] Up: Advanced Computer Algebra: The resultant Previous: Advanced Computer Algebra: The resultant
Marc Moreno Maza
2004-04-27