Exercise 2.

In the ring ${\mbox{${\mathbb{A}}$}} = {\mbox{${\mathbb{K}}$}}[x]$ of univariate polynomials with coefficients in ${\mbox{${\mathbb{K}}$}} = {\mbox{${\mathbb{Z}}$}}/17{\mbox{${\mathbb{Z}}$}}$ , we consider the polynomials $f_1 = x^2 + 1$ , $g_1 = x + 1$ , $f_2 = x^3 + x^2 + x + 1$ and $g_2 = x^2 +3x + 1$ . Using one of the FFT-based multiplication algorithms described in the course notes:

1. compute the product of the polynomials $f_1$ and $g_1$
2. compute the product of the polynomials $f_2$ and $g_2$

For each product, you should give (at least) the results of each Discrete Fourier Transforms. Of course, you should better choose primitive roots of unity that minize the number of required operations in ${\mathbb{K}}$ .

Answer 3  

Answer 4  

Answer 5  

Answer 6