Modular Gcd Algorithms in

Remark 13   Algorithm 1 computes the gcd of two primitive polynomials . Before proving this algorithm, let us check that all its computations are well defined. Consider an iteration of the loop. We assume that we have a source of primes large enough. Given a prime from this source the following polynomials are computed
• 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
The only points to clarify are the equalities and . They hold since is the gcd and which implies that divides and .

Algorithm 1

Proof. It is sufficient to see that

 (99)

both hold iff w . If the conditions hold then

 (100)

Moreover from the algorithm computations we have

 (101)

and

 (102)

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.
Therefore and have the same degree and are in fact equal up to a sign. Conversely assume that w is . Recall that and have the same degree. Then the polynomials and have the same degree too. Hence by virtue of Theorem 3 we have

 (105)

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

 (106)

Now by construction we have

 (107)

Moreover Corollary 4 states that

 (108)

which implies

 (109)

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

 (110)

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!

Remark 14   During the proof of Algorithm 1 between Relation (105) and Relation (110) we have established the following proposition which will lead to an improved algorithm.

Proposition 8   Let be as in Algorithm 1. Let be the lading coefficient of . Then we have

 (114)

Proof. From Theorem 3 and we derive Relation (105). Together with the fact that divides and the definition of this leads to Relation (106). Then Relations (105), (106) and (107) imply Relation (110) which shows .

Remark 15   From Theorem 3 we know that there are only a finite number of prime for which the relation does not hold Moreover for those prime such the polynomial has a higher degree than . Hence we can simply Algorithm 1 into Algorithm 2. as follows.

Algorithm 2

Remark 16   We aim now to realize the following improvements.
• 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 .