Questions

$(1)$

Show that $C$ is an upper bound for the coefficients of $f \, g$ computed in ${\mbox{${\mathbb{Z}}$}}[x]$ (when regarding $f$ and $g$ as polynomials of ${\mbox{${\mathbb{Z}}$}}[x]$ ).

$(2)$

Describe a modular algorithm for computing $f \, g$ in ${\mbox{${\mathbb{Z}}$}}[x]$ and give an upper for the number of machine word operations required by this algorithm.

$(3)$

Deduce an algorithm for computing $f \, g$ in ${\mbox{${\mathbb{Z}}$}}/p{\mbox{${\mathbb{Z}}$}}[x]$ and give an upper for the number of machine word operations required by this algorithm.