*If we transport the computation of a gcd from
to
we should be careful.
For instance with
*

(11) |

(12) |

*For
we will take
.
For
we will take
.
*

(13) |

*Assume from now on that
is a Unique Factorization Domain (UFD).
This means that
is an integral domain such that
*

- every irreducible is a prime
- every nonzero nonunit can be written as a product of irreducible elements in a unique way up to reordering and multiplication by units.

*The polynomial
is primitive if
.
The primitive part of
is the polynomial
such that
*

(14) |

(16) |

(17) |

Then since is primitive, with Proposition 3, we get

(18) |

- The prime elements of are the primes of plus the primitive polynomials in that are irreducible in .
- in .
- in .
- is the monic gcd of and in .

(19) |

(20) |

(21) |

(22) |

(23) |

*In fact for computing gcds in
(and more generally
over
) the modular methods (to be described
shortly) are much more efficient than going through
and the Euclidean Algorithm.
*

*The simplest approach would be
*

- to chose a large prime
- then to compute the gcd of and in (rather than )
- and to
*recover*the gcd of and in from .

- is the modular image of and that
- we have a
*reasonable*bound for the coefficients of .

*
*

2008-01-07