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.

Marc Moreno Maza
2008-03-18