next up previous
Next: A modular Gcd Algorithm in Up: Advanced Computer Algebra: The resultant Previous: Modular Gcd Algorithms in [x]

A modular Gcd Algorithm in $ \mbox{${\mathbb Z}$}$[x1,..., xn]

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$[x1,..., xn]. Algorithm 4 computes the gcd of two polynomials f, g $ \in$ $ \mbox{${\mathbb Z}$}$[x1,..., xn] 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  

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

Observations.

See [KM99] for more details and proofs.


next up previous
Next: A modular Gcd Algorithm in Up: Advanced Computer Algebra: The resultant Previous: Modular Gcd Algorithms in [x]
Marc Moreno Maza
2003-06-06