- Show that the middle product of and can easily be obtained from the remainder of by .
- Let be a primitive -th root of unity. Deduce an algorithm that computes the middle product of and at the cost of multiplying two polynomials in with degree by means of the FFT-based algorithm studied in class.

*
*

2008-03-18