Modular Gcd Algorithms in $\mbox{${\mathbb Z}$}$[x]

Remark 13   Algorithm 1 computes the gcd h of two primitive polynomials f, g $\in$ $\mbox{${\mathbb Z}$}$[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

• $\overline{{f}}$ = f modp and $\overline{{g}}$ = g modp which implies that the each coefficient c of $\overline{{f}}$ or $\overline{{g}}$ is the range [- ${\frac{{p-1}}{{2}}}$,${\frac{{p-1}}{{2}}}$]
• $\nu$ the (monic) gcd of $\overline{{f}}$ and $\overline{{g}}$ in $\mbox{${\mathbb Z}$}$/$\langle$p$\rangle$[x] (same remark for the coefficients of $\nu$)
• w $\in$ Z[x] such that w $\equiv$ b $\nu$modp (same remark for the coefficients of w)
• f ^* is q modp where q is the quotient in the division of b f by $\nu$
• g ^* is q modp where q is the quotient in the division of b g by $\nu$

The only points to clarify are the equalities f ^*  w $\equiv$ b f modp and g ^*  w $\equiv$ b g modp. They hold since w is the gcd $\overline{{f}}$ and $\overline{{g}}$ which implies that w divides b f modp and b g modp.

Algorithm 1  

Proof. It is sufficient to see that

$$\leq \leq$$ (99)

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

$$\infty \leq \leq \leq$$ (100)

Moreover from the algorithm computations we have

$$\infty$$ (101)

and

$$\equiv$$ (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 $\nu$ have the same degree since w $\equiv$ b $\nu$modp holds and since p does not divide b.
• $\nu$ 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 $\nu$ have the same degree. Then the polynomials $\nu$ and h have the same degree too. Hence by virtue of Theorem 3 we have

$$\overline{{{\alpha}}} \nu \overline{{h}}$$ (105)

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

$$\equiv \beta \equiv \nu$$ (106)

Now by construction we have

$$\infty$$ (107)

Moreover Corollary 4 states that

$$\infty \leq \infty$$ (108)

which implies

$$\beta \infty \leq$$ (109)

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

$$\beta$$ (110)

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

$$\widehat{{f}} \widehat{{g}}$$ (111)

Corollary 4 applied to ($\widehat{{f}}$, w) (as factors of b f) and ($\widehat{{g}}$, w) (as factors of b g) shows to

$$\widehat{{f}} \leq \widehat{{g}} \leq$$ (112)

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

$$\widehat{{f}} \widehat{{g}}$$ (113)

and we proved that Relation (99) holds! $\qedsymbol$

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,$\nu$, w be as in Algorithm 1. Let $\alpha$ be the lading coefficient of h. Then we have

$$\nu \Rightarrow$$ (114)

Proof. From Theorem 3 and deg(h)  =  deg($\nu$) we derive Relation (105). Together with the fact that $\alpha$ 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). $\qedsymbol$

Remark 15   From Theorem 3 we know that there are only a finite number of prime p for which the relation deg(h)  =  deg($\nu$) does not hold Moreover for those prime such deg(h)  $\neq$  deg($\nu$) 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.

This leads to Algorithm 3

Algorithm 3