離散フーリエ変換と数論変換 (1) 離散フーリエ変換 (DFT)この連載について離散フーリエ変換 (DFT) および数論変換 (NTT) の原理、そしてそれらのプログラミングにおける実装方法について記述します。 各用語の定義の違いを明確にするため、それぞれについての回を分割します。 離散フーリエ変換 (DFT) (本稿) 数列の畳み込み 高速フーリエ変換 (FFT) ビット反転置換 数論変換 (NTT) NTT の高速化 中国剰余定理による値の復元 本文今回は、離散フーリエ変換 (discrete Fourier transform, DFT) の基本的な性質と、プログラミングにおける実装方法について記述します。畳み込みのような応用や、計算の高速化には触れず、まずは原理の記述に焦点を当てます。 この連載では虚数単位を$i$で表し、インデックス (添字) を$k, j$などで表します。 また、$e^{i \theta} = \cos \theta + i
