- and which implies that the each coefficient of or is the range
- the (monic) gcd of and in (same remark for the coefficients of )
- such that (same remark for the coefficients of )
- is where is the quotient in the division of by
- is where is the quotient in the division of by

both hold iff w . If the conditions hold then

Moreover from the algorithm computations we have

and

Relations (100) and (101) imply that every coefficient of satisfies . Whereas Relation (102) tells us that every coefficient of is a multiple of . Therefore we have

(103) |

Similarly we have

(104) |

This implies that divides . Hence the primitive part of divides that of which is . On the other hand

- and have the same degree since holds and since does not divide .
- has degree equal or greater to that of by virtue of Theorem 3.

where . Since divides let be such that . Hence we have

Now by construction we have

Moreover Corollary 4 states that

(108) |

which implies

Relations (105), (106) and (107) imply

Since divides and we deduce from Relation (109) that divides and . Hence there exist polynomials and such that

(111) |

Corollary 4 applied to (as factors of ) and (as factors of ) shows to

(112) |

Finally, it follows from the way and are computed that we have in fact

(113) |

and we proved that Relation (99) holds!

- We woulk like to use a CRA scheme which would allow us to work with small primes and thus to take advantage of machine integer arithmetic.
- We know that the bound is most of the times very pessimistic. So we would like to try to exit before the bound is reached.
- We would like also to add optimizations like: when the modular gcd has degree 0 then is .

*
*

2008-01-07