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

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 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  

\fbox{
\begin{minipage}{10 cm}
\begin{description}
\item[{\bf Input:}] primitive...
...\\
\> {\bf return} {\rm normal}({\rm pp}($w$)) \\
\end{tabbing}\end{minipage}}

Proof. It is sufficient to see that

| f * |1 | w|1  $\displaystyle \leq$  B    and    | g * |1 | w|1  $\displaystyle \leq$  B (99)

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

| f * w|$\scriptstyle \infty$  $\displaystyle \leq$  | f * w|1  $\displaystyle \leq$  | f * |1 | w|1  $\displaystyle \leq$  B < p/2 (100)

Moreover from the algorithm computations we have

| b f|$\scriptstyle \infty$  <  p/2 (101)

and

f *  w  $\displaystyle \equiv$  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 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

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

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

w  $\displaystyle \equiv$  $\displaystyle \beta$ h  $\displaystyle \equiv$  b $\displaystyle \nu$modp (106)

Now by construction we have

| w|$\scriptstyle \infty$  <  p/2 (107)

Moreover Corollary 4 states that

| h|$\scriptstyle \infty$  $\displaystyle \leq$  (n + 1)1/2 2n | f|$\scriptstyle \infty$ (108)

which implies

|$\displaystyle \beta$ h|$\scriptstyle \infty$  $\displaystyle \leq$  B  <  p/2. (109)

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

w  =  $\displaystyle \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

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

|$\displaystyle \widehat{{f}}$|1 | w|1  $\displaystyle \leq$  B    and    |$\displaystyle \widehat{{g}}$|1 | w|1  $\displaystyle \leq$  B (112)

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

$\displaystyle \widehat{{f}}$  =  f *     and    $\displaystyle \widehat{{g}}$  =  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

deg(h)  =  deg($\displaystyle \nu$$\displaystyle \Rightarrow$   h  =  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  =  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  

\fbox{
\begin{minipage}{10 cm}
\begin{description}
\item[{\bf Input:}] primitive...
... {\bf and} $w \mid g$\ \\
\> {\bf return} $w$\ \\
\end{tabbing}\end{minipage}}

Remark 16   We aim now to realize the following improvements. This leads to Algorithm 3

Algorithm 3  

\fbox{
\begin{minipage}{12 cm}
\begin{description}
\item[{\bf Input:}] primitive...
...n} $h$\ \\
\> \> $(m, g_m)$\ := $(m \, p, w)$\ \\
\end{tabbing}\end{minipage}}


next up previous
Next: A modular Gcd Algorithm in Up: Advanced Computer Algebra: The resultant Previous: Mignotte's factor bound
Marc Moreno Maza
2004-04-27