Exercise 2.

In the ring ${\mbox{${\mathbb{A}}$}} = {\mbox{${\mathbb{K}}$}}[x]$ of univariate polynomials with coefficients in ${\mbox{${\mathbb{K}}$}} = {\mbox{${\mathbb{Z}}$}}/5{\mbox{${\mathbb{Z}}$}}$ , we consider the polynomials $f_1 = x^2 + x + 1$ , $f_2 = x + 1$ , $f_3 = x^3 + x^2 + x + 1$ .

For every pair $(f_i, f_j)$ , with $1 \leq i < j \leq$ such that we can compute the product $f_i f_j$ by means of the FFT-based algorithm studied in class:

1. find a suitable primitive $n$ -th root of unity in ${\mbox{${\mathbb{K}}$}}$ ,
2. compute the DFT of $f_1$ and $f_j$
3. deduce the product of the polynomials $f_i$ and $f_j$ by means of the FFT-based algorithm studied in class

Answer 3  

Answer 4  

Answer 5  

Answer 6