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.

Algorithm 4  

\begin{minipage}{12 cm}
\item[{\bf Input:}] $f,g \in ...
...n} $h$\ \\
\> \> $(m, g_m)$\ := $(m \, p, w)$\ \\


See [KM99] for more details and proofs.

Marc Moreno Maza