The two polynomial can be written as and . The product of and using FFT can be performed in the following steps...

a) if , then trasform by inserting zeroes and into polynomial of degree 2n-1...

b) perform the FFT of and calling the FFT of and the FFT of ...

c) compute the product ...

d) perform the inverse FFT of obtaining the product ...

Marry Christmas from Serbia