next up previous
Next: Gcd Algorithms in [x1,..., xn] Up: Advanced Computer Algebra: The resultant Previous: A modular Gcd Algorithm in

A modular Gcd Algorithm in E[x] with E Euclidean

We present now another generalization of Algorithm 3: the case of univariate polynomials over an Euclidean domain E with an Euclidean size $ \delta$. This idea appears in [KM99]. We need two assumptions for E.

First we assume that we have access to the stream of unassociated primes p1, p2, p3,..., such that $ \delta$(p1) < $ \delta$(p1p2) < $ \delta$(p1p2p3) < ... . Indeed the recovery of an element a in E from a modm=p1 ... pn requires sufficiently large m.

Secondly, we assume the avialability of a mapping scs from E×E $ \setminus$ {0} to E, called a symmetric canonical simplifier, such that we have the following properties.

Simplification.
Any element a $ \in$ E must satisfy a  $ \equiv$  scs(a, m) for any m $ \in$ E $ \setminus$ {0}. More formally:

($\displaystyle \forall$ a $\displaystyle \in$ E)($\displaystyle \forall$ m $\displaystyle \in$ E $\displaystyle \setminus$ {0})  a  $\displaystyle \equiv$  scs(a, m). (116)

Canonicity.
For any m $ \in$ E $ \setminus$ {0}, any two elements a, b $ \in$ E equivalent modulo m must satisfy scs(a, m)  =  scs(b, m). More formally:

($\displaystyle \forall$ a, b $\displaystyle \in$ E)($\displaystyle \forall$ m $\displaystyle \in$ E $\displaystyle \setminus$ {0})  (a  $\displaystyle \equiv$  b$\displaystyle \iff$  (scs(a, m)  =  scs(b, m)). (117)

Recoverage = symmetry.
All elements of a bounded degree are recovered by the simplifier if the modulus is sufficiently large.

($\displaystyle \forall$ B > 0)($\displaystyle \exists$ M $\displaystyle \in$ $\displaystyle \mbox{${\mathbb N}$}$)($\displaystyle \forall$ (a, m) $\displaystyle \in$ E×E $\displaystyle \setminus$ {0}) $\displaystyle \left\{\vphantom{ \begin{array}{l} {\delta}(m) \geq M(B) \\  {\delta}(a) < B \end{array} }\right.$$\displaystyle \begin{array}{l} {\delta}(m) \geq M(B) \\  {\delta}(a) < B \end{array}$  $\displaystyle \Rightarrow$   scs(a, m) = a. (118)

Algorithm 5  

\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}}

See [KM99] for more details.


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