Exercise 3.

Let $ F$ and $ G$ be two non-constant univariate polynomials with variable $ x$ and with coefficients in $ {\mbox{${\mathbb{Z}}$}}/p{\mbox{${\mathbb{Z}}$}}$ for $ p > 2$ . (In fact, what follows would work with any coefficient ring $ {\mathbb{A}}$ containing at least 4 elements and where $ 2$ is invertible.) Let $ n = 3^k$ , with $ k \in {\mbox{${\mathbb{N}}$}}$ , be the smallest power of $ 3$ such that $ F$ and $ G$ have degree less than $ n$ , but at least one of them has degree greater than or equal to $ n/3$ . (For simplicity, you can assume that $ F$ and $ G$ have the same degree $ n-1$ and that $ n$ is a power of $ 3$ .) Hence we can write

$\displaystyle F = f_2 t^2 + f_1 t + f_0 \ \ {\rm and} \ \ G = g_2 t^2 + g_1 t + g_0$ (7)

where $ f_2, f_1, f_0, g_2, g_1, g_0$ are polynomials of degree less than $ n/3$ . Let $ H$ be the product of $ F$ and $ G$ . Our goal is to design a fast algorithm for computing $ H$ . The principle is similar to Karatsuba's trick. However, the construction is a bit more involved and leads to an asymptotically faster algorithm.
(1)
Show that there exist polynomials $ h_4, h_3, h_2, h_1, h_0$ of degree less than $ 2n/3$ such that we have

$\displaystyle H = h_4 t^4 + h_3 t^3 + h_2 t^2 + h_1 t + h_0.$    

Let us regard $ F$ , $ G$ , $ H$ as polynomials in $ t$ with coefficients in $ {\mbox{${\mathbb{Z}}$}}/p{\mbox{${\mathbb{Z}}$}}[x]$ . We denote these polynomials by $ F(t)$ , $ G(t)$ , $ H(t)$ ; they have respective degrees $ 2$ , $ 2$ and $ 4$ . Observe that we have $ F(t) = G(t) H(t)$ . We evaluate $ F(t)$ and $ G(t)$ at $ t= 0$ , $ t= 1$ , $ t= -1$ and $ t= 2$ . Moreover, we define $ H(\infty) = x_2 y_2$ . Hence we have $ H(\infty) = w_4$ .
(2)
Show that computing $ H(0)$ , $ H(1)$ , $ H(-1)$ , $ H(2)$ and $ H(\infty)$ requires:
(3)
Show that $ h_4, h_3, h_2, h_1, h_0$ can be computed from $ H(\infty)$ , $ H(2)$ , $ H(-1)$ , $ H(1)$ , $ H(0)$ , by solving the following system of linear equations:

$\displaystyle \left\{ \begin{array}{rcl} H(0) &=& h_0 \\ H(1) &=& h_4 + h_3 + h...
...6 h_4 + 8 h_3 + 4 h_2 + 2 h_1 + h_0 \\ H(\infty) &=& h_4 \\ \end{array} \right.$ (8)

(4)
Show that solving this linear system can be done in $ {\cal O}(n)$ operations in $ {\mbox{${\mathbb{Z}}$}}/p{\mbox{${\mathbb{Z}}$}}$ .
Therefore, we have obtained a method for computing the ``coefficients'' $ w_4, w_3, w_2, w_1, w_0$ of $ H(t)$ . This provides, in fact, an algorithm for multiplying univariate polynomials in $ {\mbox{${\mathbb{Z}}$}}/p{\mbox{${\mathbb{Z}}$}}[x]$ . Let us estimate its time complexity. Let $ T(n)$ be the number of operations in $ {\mbox{${\mathbb{Z}}$}}/p{\mbox{${\mathbb{Z}}$}}[x]$ that are needed for computing $ H$ by means of this algorithm.
(5)
Show that $ T(n)$ satisfies a relation of the form

$\displaystyle T(n) \leq 5 T(n/3) + c n$    

where $ c$ is a constant.
(6)
Give an asymptotic upper bound for $ T(n)$ and compare with the time complexity of Karatsuba's multiplication.

Answer 4  
\fbox{
\begin{minipage}{13 cm}
\mbox{ } \\
\mbox{ } \\
\mbox{ } \\
\mbox{ } \...
...\mbox{ } \\
\mbox{ } \\
\mbox{ } \\
\mbox{ } \\
\mbox{ } \\
\end{minipage}}

Answer 5  
\fbox{
\begin{minipage}{13 cm}
\mbox{ } \\
\mbox{ } \\
\mbox{ } \\
\mbox{ } \...
...\mbox{ } \\
\mbox{ } \\
\mbox{ } \\
\mbox{ } \\
\mbox{ } \\
\end{minipage}}

Answer 6  
\fbox{
\begin{minipage}{13 cm}
\mbox{ } \\
\mbox{ } \\
\mbox{ } \\
\mbox{ } \...
...\mbox{ } \\
\mbox{ } \\
\mbox{ } \\
\mbox{ } \\
\mbox{ } \\
\end{minipage}}

Answer 7  
\fbox{
\begin{minipage}{13 cm}
\mbox{ } \\
\mbox{ } \\
\mbox{ } \\
\mbox{ } \...
...\mbox{ } \\
\mbox{ } \\
\mbox{ } \\
\mbox{ } \\
\mbox{ } \\
\end{minipage}}

Marc Moreno Maza
2008-01-31