On Euclid’s algorithm and the computation of polynomial greatest common divisors

ABSTRACT. This paper examines the computation of polynomial greatest common divisors by various generalizations of Euclid's algorithm. The phenomenon of coefficient growth is de-scribed, and the history of successful efforts first to control it and then to eliminate it is re-lated. The recently developed modular algorithm is presented in careful detail, with special atten-tion to the case of multivariate polynomials. The computing times for the classical algorithm and for the modular algorithm are analyzed, and it is shown that the modular algorithm is markedly superior. In fact, in the multivariate ease, the maximum computing time for the modular algorithm is strictly dominated by the maximum computing time for the first pseudo-division in the classical algorithm