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