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

$\displaystyle 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.$    

Marc Moreno Maza
2008-03-18