- Show that the middle product of
be obtained from the remainder of
be a primitive
-th root of unity.
Deduce an algorithm that computes the middle product of
at the cost of multiplying
two polynomials in
by means of the FFT-based algorithm studied in class.
Marc Moreno Maza