離散フーリエ変換を O(n log n) で行うアルゴリズム

離散フーリエ変換とは，長さ の数列 から長さ の数列 への変換で，各 について次のように定義されます．

ただし は で定義され， 乗すると 1 になる虚数(の1つ)です．また，逆離散フーリエ変換はその逆変換ですが，式はよく似ています． 逆離散フーリエ変換が離散フーリエ変換の逆変換になっていることの証明は容易です．

今回はこれを任意の について で計算するアルゴリズムを考えます．

Cooley-Tukey のアルゴリズム

Cooley-Tukey のアルゴリズムは離散フーリエ変換を行う最も有名なアルゴリズムで， が合成数のときに限って使えます．例として， のときを考えます． の離散フーリエ変換 は，定義によれば次のようになります．

さて，ここで を の形に因数分解します．まず ， としてみましょう．そして，右辺にある を，添字を で割った余りで並び替えます． ここで， であることを利用すると， の肩の数字が次のように書き換えられます． この状態で式を次のようにくくると，同じ形がたくさん出てきます． であることに注意すると， は長さ の数列 の離散フーリエ変換であり， は長さ の数列 の離散フーリエ変換であり， は長さ の数列 の離散フーリエ変換であるということに気付きます．これを用いてもとの式を書き換えると となり，さらにこれを並べ替えると となります．今度は ，， であることに注意すると， は長さ の数列 の離散フーリエ変換であり， は長さ の数列 の離散フーリエ変換であるということに気付きます．つまり，長さ の数列の離散フーリエ変換が，長さ の数列の離散フーリエ変換 回と，長さ の数列の離散フーリエ変換 回によって行えるわけです．
今度は， ， としてみましょう．同様の変形により となるので， の離散フーリエ変換を とし， の離散フーリエ変換を とすると， は の離散フーリエ変換であり， は の離散フーリエ変換であり， は の離散フーリエ変換であるわけです．

以上より，長さ の数列の離散フーリエ変換は，長さ の数列の離散フーリエ変換を 回行ったあとに，長さ の数列の離散フーリエ変換を 回行うことでできることが分かりました．これを繰り返していくことで， が小さな素数の積で構成されているときに で離散フーリエ変換を行うのが，Cooley-Tukey のアルゴリズムです． の最小の素因数を としてこれを繰り返すやり方を DIF (周波数間引き)， の最小の素因数を としてこれを繰り返すやり方を DIT (時間間引き)といいます．

特に が のべき乗のときの DIT が広く知られています．

フーリエ変換の性質

さて，次に が素数のときを考えるのですが，その前に離散フーリエ変換の重要な性質について見てみます．それは「畳み込み定理」と呼ばれるものです．

長さが であるような 2 つの数列 と について，その畳み込み を次のように定義します．

ただし， は と等価とします．たとえば なら畳み込みは次のようになります． このとき， の離散フーリエ変換をそれぞれ とすると任意の について が成り立つというのが畳み込み定理です．証明は次のようにできます． (ただし途中でシグマの下の数が上の数より大きくなってしまうところはその総和の結果を とします)

2020/10/25 追記：熨斗さんからより分かりやすい証明をいただきました．
多項式同士の mod を次のように定義します．

， ， を の多項式とする．ある多項式 が存在して が の恒等式となるとき， と は を法として合同であるといい， と書く．

このとき，次が成り立ちます．

の多項式 ， ， が を満たすとき， であるような任意の について が成り立つ．

さて， が と の巡回畳み込みであるとき，



とおくと が成り立ちます． は を満たすので， すなわち となるわけです．

原始根

さて，突然ですが数論の話をします． を素数とし， を 以上 未満の自然数とします．このとき， を満たす最小の自然数 を， を法とした の「位数」といい， と書きます． の位数 は常に の約数です．なぜなら，フェルマーの小定理より であり，もし でないと仮定すると を で割った余り は を満たすので， ではなく が の位数となるはずだからです．

「 が の原始根である」とは， であることをいいます．

が の原始根であるとき， を で割った余りは を並べ替えたものになります．なぜなら任意の について より だからです．

が の原始根かどうかは，で判定できます．もし が原始根でない，すなわち ならば， は全て と合同になるはずです．ということは，逆に の各素因数 について を調べ上げれば，その中に必ず と合同なものが含まれるはずです．もし含まれなければ， は の原始根です．

任意の奇素数 に少なくとも 1 つ原始根が存在します．証明は難しいので省略しますが，整数 が の原始根でなければ， のいずれとも合同でない数 をとってくることで， の位数が の位数よりも大きくなります．これを繰り返すと，いつか位数が であるような数が見つかります(ただし，実際に原始根を求めるコードを書くときは， 以上 未満の自然数について順に原始根かどうか確かめていくだけで十分高速に動作します)．

Rader のアルゴリズム

離散フーリエ変換の話に戻ります．Rader のアルゴリズムは， が 以上の素数のときに使えるアルゴリズムです． は合成数なので，長さ の数列の離散フーリエ変換を長さ の数列の離散フーリエ変換で表し， Cooley-Tukey のアルゴリズムを適用します．

例として， の場合を考えます．

まず の原始根 を発見します．今回は が原始根なので とします．このとき， を で割った余りはそれぞれ なので， 〜 について次のような書き換えが可能です． 少し混乱しますが落ち着いて確認しましょう．たとえば における の係数というのはもともと で，この右肩の という値は という計算によって得られたものでした．今度はこれが ， という式で書き換えられて， になっています．こうして掛け算が指数の足し算になったところで，さらに を使うことで，最終的には となります．これはまさしく，数列 と数列 の畳み込みです．よって，これらを離散フーリエ変換して積を計算し，逆離散フーリエ変換でもとにもどしてやれば計算できます．

よって，Cooley-Turkey のアルゴリズムと Rader のアルゴリズムを組み合わせて使うことで，任意の自然数 に対して で離散フーリエ変換を計算することができます．

最後まで読んでくださってありがとうございましたm(_ _)m