A modular Gcd Algorithm in $\mbox{${\mathbb Z}$}$[x₁,..., x_n]

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 $\mbox{${\mathbb Z}$}$/$\langle$p$\rangle$[x₁,..., x_n]. Algorithm 4 computes the gcd of two polynomials f, g $\in$ $\mbox{${\mathbb Z}$}$[x₁,..., x_n] with this assumption. Observe that Algorithm 4 takes as input any couple of multivariate polynomials over $\mbox{${\mathbb Z}$}$, primitive or not.

Algorithm 4 relies also on the following technical assumptions.

• f $\in$ $\mbox{${\mathbb Z}$}$[x₁,..., x_n]  $\longmapsto$  content_{$\mbox{${\mathbb Z}$}$}(f ) computes the content of a multivariate polynomial over $\mbox{${\mathbb Z}$}$, that is the gcd of its coefficients. We make the same conventions as for the univariate case. See Definition 3.
• (f $\in$ $\mbox{${\mathbb Z}$}$[x₁,..., x_n], c $\in$ R)  $\longmapsto$  f exquo c is the exact division of a polynomial by an integer. That is, assuming that c divides f, the value returned by f $\sf exquo$ c is the polynomial g such that f = c g.
• 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 $\mbox{${\mathbb Z}$}$. To decide which is the leading monomial (and thus which is the leading coefficient) we assume that the variables are totally ordered, say x₁ > ^... > x_n. Then to order monomials we use the lexicographic ordering induced by x₁ > ^... > x_n.
• f $\in$ $\mbox{${\mathbb Z}$}$[x₁,..., x_n]  $\longmapsto$  lc_lex(f ) returns the leading coefficient of f w.r.t. the lexicographic ordering induced by x₁ > ^... > x_n.
• f $\in$ $\mbox{${\mathbb Z}$}$[x₁,..., x_n]  $\longmapsto$  deg_lex(f ) returns the degreeof f w.r.t. the lexicographic ordering induced by x₁ > ^... > x_n. That is the exponent vector of the leading monomial of f.

Algorithm 4  

Observations.

• The assumption of primtive input polynomials has been relaxed. However by dividing f and g by their contents, we turn back to the primitive case.
• The combine(p, m)(g_p, g_m) is in fact a series of CRA: one per monomial. Remember the case of the fast multication in $\mbox{${\mathbb Z}$}$[x] based on the FFT.
• Note that the result computed by the Chinese remainder algorithm (CRA) must be expressed in the symmetric range of the integers modulo m p so that negative integer coefficients in w can be reconstructed as well as positive ones.
• The termination test can be improved in the sense that it may not be worth trying it before a certain amount of modular gcd have been computed. In practice, one could wait for the following stabilization condition

  g_m = w (115)

  
  
  which will necessarily happen.

See [KM99] for more details and proofs.