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
The polynomial
is primitive if
.
The primitive part of
is the polynomial
such that
![]() |
(14) |
![]() |
(16) |
![]() |
(17) |
![]() |
(18) |
![]() |
(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
Marc Moreno Maza