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 \mod{p}$ and $\overline{g} = g \mod{p}$ 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} \mod{p}$ (same remark for the coefficients of $w$ )
• $f^{\ast}$ is $q \mod{p}$ where $q$ is the quotient in the division of $b \, f$ by ${\nu}$
• $g^{\ast}$ is $q \mod{p}$ where $q$ is the quotient in the division of $b \, g$ by ${\nu}$

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

Algorithm 1  

Proof. It is sufficient to see that

$${\Vert f^{\ast} \Vert}_1 \, {\Vert w \Vert}_1 \ \leq \ B \ \ \ \ {\rm and} \ \ \ \ {\Vert g^{\ast} \Vert}_1 \, {\Vert w \Vert}_1 \ \leq \ B$$ (99)

both hold iff ${\rm normal}({\rm pp}($ w$)) = h$ . If the conditions hold then

$${\Vert f^{\ast} w \Vert}_{\infty} \ \leq \ {\Vert f^{\ast} w \Vert}_1 \ \leq \ {\Vert f^{\ast} \Vert}_1 \, {\Vert w \Vert}_1 \ \leq \ B < p/2$$ (100)

Moreover from the algorithm computations we have

$${\Vert b \, f \Vert}_{\infty} \ < \ p/2$$ (101)

and

$$f^{\ast} \, w \ \equiv \ b \, f \mod{p}$$ (102)

Relations (100) and (101) imply that every coefficient $c$ of $f^{\ast} \, w - b \, f$ satisfies $-p < c < p$ . Whereas Relation (102) tells us that every coefficient $c$ of $f^{\ast} \, w - b \, f$ is a multiple of $p$ . Therefore we have

$$f^{\ast} \, w \ = \ b \, f$$ (103)

Similarly we have

$$g^{\ast} \, 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} \mod{p}$ holds and since $p$ does not divide $b$ .
• ${\nu}$ has degree equal or greater to that of $h$ by virtue of Theorem 3.

Therefore ${\rm pp}(w)$ and $h$ have the same degree and are in fact equal up to a sign. Conversely assume that ${\rm normal}({\rm 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} = {\rm lc}(h)$ . Since ${\alpha}$ divides $b$ let ${\beta}$ be such that $b = {\alpha} \, {\beta}$ . Hence we have

$$w \ \equiv \ {\beta} \, h \ \equiv \ b \, {\nu} \mod{p}$$ (106)

Now by construction we have

$${\Vert w \Vert}_{\infty} \ < \ p/2$$ (107)

Moreover Corollary 4 states that

$${\Vert h \Vert}_{\infty} \ \leq \ (n + 1)^{1/2} \, 2^{n} \, {\Vert f \Vert}_{\infty}$$ (108)

which implies

$${\Vert {\beta} \, h \Vert}_{\infty} \ \leq \ B \ < \ p/2.$$ (109)

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

$$w \ = \ {\beta} \, 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 $\widehat{f}$ and $\widehat{g}$ such that

$$\widehat{f} \, w \ = \ b \, f \ \ \ \ {\rm and} \ \ \ \ \widehat{g} \, w \ = \ b \, 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

$${\Vert \widehat{f} \Vert}_1 \, {\Vert w \Vert}_1 \ \leq \ B \ \ \ \ {\rm and} \ \ \ \ {\Vert \widehat{g} \Vert}_1 \, {\Vert w \Vert}_1 \ \leq \ B$$ (112)

Finally, it follows from the way $f^{\ast}$ and $g^{\ast}$ are computed that we have in fact

$$\widehat{f} \ = \ f^{\ast} \ \ \ \ {\rm and} \ \ \ \ \widehat{g} \ = \ g^{\ast}$$ (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

$${\deg}(h) \ = \ {\deg}({\nu}) \ \ \Rightarrow \ \ h \ = \ {\rm pp}(w).$$ (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 \ = \ {\rm 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