Questions

$ (1)$
Consider the particular case where $ d' = 4 \, d$ , $ r =2$ and $ M(d) = 2 d^2$ . Compare the costs of the following two approaches:
  1. compute first the remainder $ r_{12} = f \mod{\ m_1 m_2}$ and then, the remainders $ r_1 = r_{12} \mod{\ m_1}$ and $ r_2 = r_{12} \mod{\ m_2}$ ,
  2. compute the remainders $ f \mod{\ m_1}$ and $ f \mod{\ m_2}$ directly.
$ (2)$
Using a divide-and-conquer strategy, show that all remainders $ f \mod{\ m_1}, \ldots, f \mod{\ m_r}$ can be computed in $ O({\sc M}(d) \, {\log} \, d)$ operations in $ {\mathbb{R}}$ .

Marc Moreno Maza
2008-03-18