Statement

Let ${\mathbb{R}}$ be a commutative ring. Let $d \longmapsto {\sc M}(d)$ be a multiplication time. Hence, for any two polynomials $f, g \in {\mbox{${\mathbb{R}}$}}[x]$ of degree less than $d$ one can compute the product $fg$ in at most ${\sc M}(d)$ operations in ${\mathbb{R}}$ . Moreover, for all $d' \geq d \geq 0$ we have ${\sc M}(d') + {\sc M}(d) \leq {\sc M}(d'+d)$ .

Let $d' \geq d > 0$ be two integers. Let $f \in {\mbox{${\mathbb{R}}$}}[x]$ be of degree $d'$ and let $m_1, \ldots, m_r \in {\mbox{${\mathbb{R}}$}}[x]$ be monic polynomials such that the sum of their degrees ${\deg} \, m_1 + \cdots + {\deg} \, m_r$ is $d$ .

The goal of this exercise is to show that all remainders $f \mod{\ m_1}, \ldots, f \mod{\ m_r}$ can be computed in $O({\sc M}(d) \, {\log} \, d + {\sc M}(d') )$ operations in ${\mathbb{R}}$ .

The following result (to be proved in class) will be essential: division-with-remainder of a polynomial $a \in {\mbox{${\mathbb{R}}$}}[x]$ of degree $n + m$ by a monic polynomial $b \in {\mbox{${\mathbb{R}}$}}[x]$ of degree $n$ (where $n, m$ are non-negative integers) can be done in at most $D(m,n)$ ring operations in ${\mathbb{R}}$ where we have

$$D(m,n) = \left\{ \begin{array}{lcr} 4 {\sc M}(m) + {\sc M}(n) + O... ... m \leq n, \\ 5 {\sc M}(m) + O(m) & {\rm if} & m \geq n. \\ \end{array} \right.$$