For every pair , with such that we can compute the product by means of the FFT-based algorithm studied in class:

- find a suitable primitive -th root of unity in ,
- compute the DFT of and
- deduce the product of the polynomials and by means of the FFT-based algorithm studied in class

2008-01-31