Elements of correction

$(1)$

Assume that $g$ divides $f$ and let $q$ be the quotient. The degree of $q$ is $m -n$ . Viewing $f$ , $g$ and $q$ as polynomials in ${\mbox{${\mathbb{Q}}$}}[x]$ one can use Lagrange interpolation to construct $q$ from its values at $0, 1, \ldots, m-n$ . This idea leads to the following algorithm.

$(a)$

Let $i = 0$ .

$(b)$

While $i \leq m-n$ repeat

$(b1)$

Compute $f(i)$ and $g(i)$ .

$(b2)$

If $g(i)$ does not divide $f(i)$ in ${\mathbb{Z}}$ then return ``g does not divide f'' otherwise define $q(i) = f(i) / g(i)$ .

$(b3)$

$i = i + 1$ .

$(c)$

Interpolate $(0, q(0)), \ldots, (m-n, q(m-n))$ in order to get $q$ and return it.

$(2)$

Assume again that $g$ divides $f$ and let $q$ be the quotient. This means that $f = g q$ in ${\mbox{${\mathbb{Z}}$}}[x]$ . Let $C$ be an upper for the absolute value of a coefficient in $q$ . (Actually, one can adapt Exercise 1 in order to obtain such a bound). Let $p$ be a prime number. Then, we have $f \equiv g q \mod{\ p}$ . This idea leads to the following algorithm.

$(a)$

Let $p_1 < \cdots < p_r$ be machine-word-size odd primes such that their product $m$ exceeds $2 C$

$(b)$

For all $i = 1 \cdots r$ repeat:

$(b1)$

compute the images $f_i$ and $g_i$ of $f$ and $g$ in ${\mbox{${\mathbb{Z}}$}}/p_i{\mbox{${\mathbb{Z}}$}}[x]$ ,

$(b2)$

compute the quotient $q_i$ and remainder $r_i$ in the division of $f_i$ by $g_i$ in ${\mbox{${\mathbb{Z}}$}}/p_i{\mbox{${\mathbb{Z}}$}}[x]$ ,

$(b3)$

if $r_i \neq 0$ then return ``g does not divide f''

$(c)$

Use the Chinese Remainder Algorithm coefficient-wise in order to construct a polynomial $q$ from $q_1, \ldots, q_r$ .

$(d)$

If $f - q g \neq 0$ then return ``g does not divide f'' otherwise return $q$ .

The checking statement $(d)$ can be avoided but this requires additional material outside of the scope of this course.

$(3)$

The second approach is probably better since it is a modular method relying on modular computations over machine-word-size finite fields. But, of course, the bound $C$ has to be sharp.