$n$ 次多項式 $f(x) = \sum_{p=0}^{n-1} a_p x^p$ から、以下で定義される $n$ 次多項式 $\hat{f}$ への写像を 離散 Fourier(フーリエ)変換 という。ここで $\omega_n$ は $1$ の原始 $n$ 乗根。 $$ \hat{f}(t) = \sum_{k=0}^{n-1}