# A modular Gcd Algorithm in

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.

• The assumption of primtive input polynomials has been relaxed. However by dividing and by their contents, we turn back to the primitive case.
• The combine( )( ) is in fact a series of CRA: one per monomial. Remember the case of the fast multication in 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 so that negative integer coefficients in 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

 (115)

which will necessarily happen.
See [KM99] for more details and proofs.

Marc Moreno Maza
2008-01-07