- Assume that
divides
and let
be the quotient.
The degree of
is
.
Viewing
,
and
as polynomials in
one can use Lagrange interpolation to construct
from its values at
.
This idea leads to the following algorithm.
- Let .
- While
repeat
- Compute and .
- If does not divide in then return ``g does not divide f'' otherwise define .
- .

- Interpolate in order to get and return it.

- Assume again that
divides
and let
be the quotient.
This means that
in
.
Let
be an upper for the absolute value of a coefficient in
.
(Actually, one can adapt Exercise 1 in order to obtain such a bound).
Let
be a prime number.
Then, we have
.
This idea leads to the following algorithm.
- Let be machine-word-size odd primes such that their product exceeds
- For all
repeat:
- compute the images and of and in ,
- compute the quotient and remainder in the division of by in ,
- if then return ``g does not divide f''

- Use the Chinese Remainder Algorithm coefficient-wise in order to construct a polynomial from .
- If then return ``g does not divide f'' otherwise return .

*checking statement*can be avoided but this requires additional material outside of the scope of this course. - The second approach is probably better since it is a modular method relying on modular computations over machine-word-size finite fields. But, of course, the bound has to be sharp.

*
*

2008-03-18