Exercise 3.

Explain how one could use the FFT-based polynomial multiplication techniques in order to compute the product of two polynomials $f, g \in {\mbox{${\mathbb{Z}}$}}[x]$ with degree less than $n$ . Several approaches are possible. You are asked to describe at least one. (Note that one is given in the course notes.) Suggesting another approach would add a bonus of 5 points.

Answer 7