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_1, p_2, p_3, \ldots,$ such that ${\delta}(p_1) < {\delta}(p_1 p_2) < {\delta}(p_1 p_2 p_3) < \cdots$ . Indeed the recovery of an element $a$ in $E$ from $a \mod{m=p_1 \cdots p_n}$ requires sufficiently large $m$ .

Secondly, we assume the avialability of a mapping ${\mbox{\sf scs}}$ from $E \times 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 \ {\mbox{\sf scs}}(a,m)$ for any $m \in E \setminus \{ 0\}$ . More formally:

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

Canonicity.

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

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

Recoverage = symmetry.

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

$$({\forall} \ B > 0) ({\exists} \ M \in {\mbox{${\mathbb{N}}$}}) (... ...elta}(a) < B \end{array} \right. \ \ \Rightarrow \ \ {\mbox{\sf scs}}(a,m) = a.$$ (118)

Algorithm 5  

See [KM99] for more details.