Algorithm 3
can be adapted to the case of more than one variable provided
that we have a gcd algorithm in polynomial rings of the
form
.
Algorithm 4
computes the gcd of two polynomials
with this assumption.
Observe that Algorithm 4
takes as input any couple of multivariate polynomials over
,
primitive or not.
Algorithm 4
relies also on the following technical assumptions.

computes the content of a multivariate polynomial over
,
that is the gcd of its coefficients.
We make the same conventions as for the univariate case.
See Definition 3.

is
the exact division of a polynomial by an integer. That is, assuming
that
divides
, the value returned by
is the polynomial
such that
.
 We need to specify what the leading coefficient and the degree of a multivariate
polynomial are. To do so, we view polynomials as linear combinations of monomials
with coefficients in
. To decide which is the leading monomial
(and thus which is the leading coefficient) we assume that the
variables are totally ordered, say
.
Then to order monomials we use the lexicographic ordering induced by
.

returns the leading coefficient of
w.r.t. the lexicographic ordering
induced by
.

returns the degreeof
w.r.t. the lexicographic ordering
induced by
. That is the exponent vector
of the leading monomial of
.
Algorithm 4
Observations.
See [KM99] for more details and proofs.
Marc Moreno Maza
20080107