  We analyze the behavior of the Euclidean algorithm applied to pairs (g,f) of
univariate nonconstant polynomials over a finite field F_q of q elements when
the highest-degree polynomial g is fixed. Considering all the elements f of
fixed degree, we establish asymptotically optimal bounds in terms of q for the
number of elements f which are relatively prime with g and for the average
degree of gcd(g,f). The accuracy of our estimates is confirmed by practical
experiments. We also exhibit asymptotically optimal bounds for the average-case
complexity of the Euclidean algorithm applied to pairs (g,f) as above.
