Next: Gcd Algorithms in [x₁,..., x_n] 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 p₁, p₂, p₃,..., such that $\delta$ (p₁) < $\delta$ (p₁p₂) < $\delta$ (p₁p₂p₃) < ^.... Indeed the recovery of an element a in E from a modm=p₁^...p_n 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: Gcd Algorithms in [x₁,..., x_n] Up: Advanced Computer Algebra: The resultant Previous: A modular Gcd Algorithm in

Marc Moreno Maza
2004-04-27