## Elements of correction

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 .
The 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.

Marc Moreno Maza
2008-03-18