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}}$ .