>>> def fft_mul(C1, C2):Takes O(n logn) time. The idea is to right pad each polynomial with enough zeros so that the cyclic convolution becomes a noncyclic convolution. For more speed, pad
... d = len(C1)+len(C2)-1
... c1 = FFT.fft(list(C1) +  * (d-len(C1)))
... c2 = FFT.fft(list(C2) +  * (d-len(C2)))
... return list(FFT.inverse_fft(c1*c2)[:d].real)
>>> fft_mul([1,2,3],[4,5]) # (1+2*x+3*x**2)*(4+5*x)
[4.0, 13.0, 22.0, 15.0]
c2so each has power-of-2 length. (Source Code).
I posted the algorithm  on Wikipedia (alternate link: ).