# A modular Gcd Algorithm in with Euclidean

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

First we assume that we have access to the stream of unassociated primes such that . Indeed the recovery of an element in from requires sufficiently large .

Secondly, we assume the avialability of a mapping from to , called a symmetric canonical simplifier, such that we have the following properties.

Simplification.
Any element must satisfy for any . More formally:

 (116)

Canonicity.
For any , any two elements equivalent modulo must satisfy . More formally:

 (117)

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

 (118)

Algorithm 5

See [KM99] for more details.

Marc Moreno Maza
2008-01-07