FFT

$$F(x)=\sum _i{a}_i{x}^i=G(x^2)+xH(x^2)$$

NTT