A modular Gcd Algorithm in ${\mbox{${\mathbb{Z}}$}}[x_1, \ldots, 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_1, \ldots, x_n]$ . Algorithm 4 computes the gcd of two polynomials $f,g \in {\mbox{${\mathbb{Z}}$}}[x_1, \ldots, 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_1, \ldots, x_n] \ \longmapsto \ {\rm 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_1, \ldots, x_n], c \in R) \ \longmapsto \ f \ \mbox{{\sf 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_1 > \cdots > x_n$ . Then to order monomials we use the lexicographic ordering induced by $x_1 > \cdots > x_n$ .
• $f \in {\mbox{${\mathbb{Z}}$}}[x_1, \ldots, x_n] \ \longmapsto \ {\rm lc}_{lex}(f)$ returns the leading coefficient of $f$ w.r.t. the lexicographic ordering induced by $x_1 > \cdots > x_n$ .
• $f \in {\mbox{${\mathbb{Z}}$}}[x_1, \ldots, x_n] \ \longmapsto \ {\deg}_{lex}(f)$ returns the degreeof $f$ w.r.t. the lexicographic ordering induced by $x_1 > \cdots > 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.