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

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

$$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:

• 5 multiplications of polynomials with degree less than $n/3$ ,
• 12 additions or subtractions of polynomials with degree less than $n/3$ ,
• 4 multiplications of a polynomial with degree less than $n/3$ by a power of $2$ (actually $2$ or $4$ ).

(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:

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

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

Answer 5  

Answer 6  

Answer 7