Abstract
This paper examines the computation of polynomial greatest common divisors by various generalizations of Euclid's algorithm. The phenomenon of coefficient growth Is described, and the history of successful efforts first to control it and then to eliminate it is related.
The recently developed modular algorithm is presented in careful detail, with special attention to the case of multivariate polynomials .
The .computing times for the subresultant PRS algorithm, which Is essentially the best of its kind, and for the modular algorithm are analyzed, and it Is shown that the modular algorithm is markedly superior. In fact, the modular algorithm can obtain a GCD in less time than Is required to verify it by classical division.
1. Introduction
1.1 Origin and Scope
According to Knuth [l, p. 294], "Euclid's algorithm, which is found in Book 7, Propositions 1 and 2 of his Elements (c. 300 B.C.), and which many scholars conjecture was actually Euclid's rendition of an algorithm due to Eudoxus (c. 375 B.C.),... is the oldest nontrivial algorithm which has survived to the present day."
The algorithm, as presented by Euclid, computes the positive greatest common divisor of two given positive Integers. However it is readily generalized to apply to polynomials in one variable over a field, and further to polynomials in any number of variables over any unique factorization domain in which greatest common divisors can be computed.
In particular, we shall focus our attention on domains of univariate or multivariate polynomials (that ls~| polynomials In one or several variables, respectively) over the integers or the rationale, even though some of the results will be stated more generally.
We shall not consider polynomials with real coefficients, because the reals are not exactly representable in a computer, and any use of finite precision operations can make it Impossible to test whether one polynomial divides another,, or even to determine the degree of a polynomial. Although there may be special situations in which these obstacles can usefully be attacked, it is clear that they cannot be overcome In any general way.
1.2 Applications
The problem of computing GCD's has recently received considerable attention
because of the need to simplify rational numbers (quotients of integers) and rational functions (quotients of polynomials) in systems for mechanized algebra [2]. However, Euclid's algorithm is also intimately connected with continued fractions [1, pp. 316-320], diophantine equations [1,' p. 303 ], blgradients [3j4]j Sturm sequences [5, chap j], and elimination theory [5, chap 12] (including resultants and discriminants).
1.3 Basic Concepts
Before proceeding further, let us review some basic concepts. In an integral domain, divisors of unity are called units, and elements which divide each other are called associates; clearly the ratio of two associates is a unit. In a field, all nonzero elements are units; in the domain of integers, however, the only units are 1 and -1.
An element of an integral domain Is said to be irreducible if its only divisors are units and associates. An integral domain in which every element can be represented uniquely (up to associativity) as a product of Irreducibles Is called a unique factorization domain.
The relation of associativity is an equivalence relation, and can therefore be used to decompose an integral domain into associate classes. It is often convenient to single out one element of each associate class as a canonical representative, and define it to be unit normal. In the domain of integers, all nonnegative integers are unit normal. In a field, since all nonzero elements are units, only 0 and 1 are unit normal. In a domain of polynomials, those with unit-normal leading coefficients are unit normal.
Let ai,...,an be given nonzero elements of an integral domain. Then g is called the greatest common divisor (GCD) of a^,...,an If and only if
(a) g divides aj,,,,,anJ
(b) every divisor of a^,...,an divides g, and
(c) g is unit normal.
In a unique factorization domain there is always a unique GCD g = gcd(a1,...,an). If g = 1, we say that a-^, . . . ,an are relatively prime.
1.4 The Algorithm for Integers
We now present Euclid's algorithm for computing the GCD of positive Integers a^ and &2 with a^ >^ &2. • Setting a± = a^.gmod aj__]_, for i = ЗЛ>5, .. ., we obtain a strictly decreasing sequence of positive integers, whose last nonzero element is the desired GCD.
195
