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₁ = x² + 1, g₁ = x + 1, f₂ = x³ + x² + x + 1 and g₂ = x² + 3x + 1. Using one of the FFT-based multiplication algorithms described in the course notes:

1. compute the product of the polynomials f₁ and g₁
2. compute the product of the polynomials f₂ and g₂

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