Elements of correction

$(1)$

Define $h = fg$ in ${\mbox{${\mathbb{Z}}$}}[x]$ . Assume that $f$ and $g$ have degree $d$ and define:

$$f = f_d x^d + \cdots + f_1 x + f_0 \ \ {\rm and} \ \ g = g_d x^d + \cdots + g_1 x + g_0.$$ (18)

Then define:

$$h = c_{2d} x^{2d} + \cdots + c_1 x + c_0.$$ (19)

For all $0 \leq k \leq 2d$ , we have:

$$c_k = {\sum}_{i+j=k} \, f_i g_j.$$ (20)

Observe that, for a given $k$ in the range $0 \cdots 2d$ , the number of products $f_i g_j$ is at most $d+1$ . Indeed, the polynomials $f$ and $g$ have $d+1$ terms. From there, we deduce that for all $0 \leq k \leq 2d$ , we have:

$$\mid c_k \mid \ \leq \ (d+1) B^2.$$ (21)

$(2)$

One can proceed as follows:

$(a)$

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

$(b)$

For all $i = 1 \cdots r$ compute

$(b1)$

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

$(b2)$

the product $h_i = f_i \, g_i$ in ${\mbox{${\mathbb{Z}}$}}/p_i{\mbox{${\mathbb{Z}}$}}[x]$ .

$(c)$

Using the Chinese Remaindering Algorithm coefficient-wise, reconstruct $f\,g$ from $h_1, \ldots, h_r$ .

$(3)$

We give complexity estimates (upper bounds for the number of machine-word operations) for each of the steps $(b1)$ , $(b2)$ and $(c)$ above. For the operations on integers, we use bounds based on classical quadratic algorithms (not fast ones, since they were not discussed in class). Let $N$ be the length of a machine-word, let ${\ell}_B = \lfloor {\log}_2 (B / N) \rfloor + 1$ be the number of machine-words to write $B$ and let ${\ell}_C = \lfloor {\log}_2 (C / N) \rfloor + 1$ to write $C$ .

$(b1)$

$2 \, r\, (d+1) \, O({{\ell}_B}^2)$ machine-word operations

$(b2)$

$r \, O(d \, {\log}(d) {\log}{\log}(d))$ machine-word operations

$(c)$

$(2d + 1) O({{\ell}_C}^2)$ machine-word operations