Next: A modular Gcd Algorithm in Up: Advanced Computer Algebra: The resultant Previous: Mignotte's factor bound

Modular Gcd Algorithms in [x]

Remark 13   Algorithm 1 computes the gcd h of two primitive polynomials f, g [x]. 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 p from this source the following polynomials are computed
• = f modp and = g modp which implies that the each coefficient c of or is the range [- ,]
• the (monic) gcd of and in /p[x] (same remark for the coefficients of )
• w Z[x] such that w b modp (same remark for the coefficients of w)
• f * is q modp where q is the quotient in the division of b f by
• g * is q modp where q is the quotient in the division of b g by
The only points to clarify are the equalities f *  w b f modp and g *  w b g modp. They hold since w is the gcd and which implies that w divides b f modp and b g modp.

Algorithm 1

Proof. It is sufficient to see that

 | f * |1 | w|1   B    and    | g * |1 | w|1   B (99)

both hold iff normal(pp(w)) = h. If the conditions hold then

 | f * w|   | f * w|1   | f * |1 | w|1   B < p/2 (100)

Moreover from the algorithm computations we have

 | b f|  <  p/2 (101)

and

 f *  w   b f modp (102)

Relations (100) and (101) imply that every coefficient c of f *  w - b f satisfies - p < c < p. Whereas Relation (102) tells us that every coefficient c of f *  w - b f is a multiple of p. Therefore we have

 f *  w  =  b f (103)

Similarly we have

 g *  w  =  b g (104)

This implies that w divides gcd(b f, b g). Hence the primitive part of w divides that of gcd(b f, b g) which is h. On the other hand
• w and have the same degree since w b modp holds and since p does not divide b.
• has degree equal or greater to that of h by virtue of Theorem 3.
Therefore pp(w) and h have the same degree and are in fact equal up to a sign. Conversely assume that normal(pp(w)) is h. Recall that w and have the same degree. Then the polynomials and h have the same degree too. Hence by virtue of Theorem 3 we have

 = (105)

where = lc(h). Since divides b let be such that b =  . Hence we have

 w    h   b modp (106)

Now by construction we have

 | w|  <  p/2 (107)

Moreover Corollary 4 states that

 | h|   (n + 1)1/2 2n | f| (108)

which implies

 | h|   B  <  p/2. (109)

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

 w  =   h (110)

Since h divides f and g we deduce from Relation (109) that w divides b f and b g. Hence there exist polynomials and such that

 w  =  b f    and     w  =  b g (111)

Corollary 4 applied to (, w) (as factors of b f) and (, w) (as factors of b g) shows to

 ||1 | w|1   B    and    ||1 | w|1   B (112)

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

 =  f *     and      =  g * (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 f, g, h, p,, w be as in Algorithm 1. Let be the lading coefficient of h. Then we have

 deg(h)  =  deg()    h  =  pp(w). (114)

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

Remark 15   From Theorem 3 we know that there are only a finite number of prime p for which the relation deg(h)  =  deg() does not hold Moreover for those prime such deg(h  deg() the polynomial w has a higher degree than h. 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 B 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 h is 1.