離散フーリエ変換 (一般)

数学において、環上の離散フーリエ変換は、複素数上の離散フーリエ変換を一般化したものである。
定義.
formula_1 を任意の環、formula_2 を自然数とする。formula_3 を、formula_1 の単位元の主 formula_5 乗根(principal root)であり次式を満たす要素とする
離散フーリエ変換は、formula_1 の要素の"n"個組 formula_8 を、次の計算式により formula_1 の要素の"n"個組 formula_10 へ写像する。
慣例により、formula_8 は"時間領域"にあると言い、添え字 formula_13 を"時刻"と呼ぶ。また、formula_10 は"周波数領域"にあると言い、formula_15 を"周波数"と呼ぶ。また、formula_10 はformula_8の"周波数スペクトル"とも呼ばれる。この用語は、フーリエ変換の信号処理への応用からきている。
もし環 formula_1 が整域（体の場合を含む)であるとき、formula_19は単位元の原始"n"乗根であれば十分であり、条件式(1)は、以下で置き換えることができる。
証明：formula_21に対して、formula_23 と置く。formula_24 であるから、formula_25 であり、
が成り立つ。formula_19 は原始"n"乗根であるから、formula_28 が成り立つ。 formula_1 が整域であれば、零因子を持たないため、和 formula_30 は零である。∎
もう一つのシンプルな条件は、"n"が２のべき乗のときである。この場合、条件式(1)は formula_31 でおきかえることができる。
逆変換.
逆離散フーリエ変換は、以下の式で与えられる：
ここで、formula_33 は formula_1 における formula_5 の乗法逆元である。（もしこれが存在しないならば、DFTは逆変換できない。）
証明：式(2)を式(3)の右辺に代入すると
が得られる。formula_37 ならば formula_38 であり（式(1)で formula_39 と置けばよい）、 formula_40 ならば formula_41 が成り立つので、上の式は formula_42 とちょうど一致する。∎
行列表現.
離散フーリエ変換は線形写像であるから、行列積で表現できる。行列表現では、離散フーリエ変換は以下のように書ける。
この行列は、DFT行列と呼ばれる。
同様に、逆離散フーリエ変換は
と表せる。
多項式表現.
"n"個組 formula_8 を formula_46 次の多項式
と見做すと便利なことがある。離散フーリエ変換の定義式(2)の和を書き下すと、
となる。つまり、formula_49 は多項式 formula_50 の formula_51 における値であり、
と書ける。したがって、離散フーリエ変換は、多項式の"係数"を"値"に変換するもの考えることができる。係数は時間領域で、値は周波数領域にある。もちろん、多項式の値は、単位元のformula_5 乗根（formula_19 とその2乗、3乗、4乗、...）において評価することが重要である。
同様に、逆離散フーリエ変換の式(3)を書き下すと
である。多項式を
とすれば、
が成り立つ。
以上をまとめると、以下のようになる。 もし、多項式 formula_58 の値が多項式 formula_59 の係数であるならば、（定数倍と順番の入れ替えを除けば）formula_59 の値は formula_58 の係数と等しい。
特殊な場合.
複素数.
環として複素数体 formula_62 を考えると、1のformula_5乗根は複素平面上の単位円上にある。
と定義すれば、通常の離散フーリエ変換の式
が得られる。
正規化のため、逆方向の変換IDFT（式(3)）では係数 formula_66 がかかるが、複素数の離散フーリエ変換においては、係数 formula_67 を順方向の変換DFTと逆方向の変換IDFTの両方にかけることもある。この正規化方法だと、DFT行列はユニタリ行列となる。 （formula_68 は、任意の体においては意味を持たないことに注意。）
有限体.
環として有限体 formula_69 （formula_70 は素数のべき乗）を考えた場合には、 単位元の原始"n"乗根の存在は自動的に formula_5 が formula_72 を割り切ることを意味する。 これは、各元の位数は体 formula_73 の乗法群のサイズを必ず割り切り、乗法群のサイズは formula_72 であることから言える。 これは、特に formula_75 が乗法逆元を持つことを保証し、式(3)における formula_66 はその逆元である。formula_77 上での離散フーリエ変換の応用として、符号理論におけるリード・ソロモン符号やBCH符号の復号がある。これは、円分高速フーリエ変換といった効率の良いアルゴリズムによって実行可能である。
数論変換.
数論変換（number-theoretic transform, NTT、あるいは数論的変換）は、環を formula_78 に限定した場合の離散フーリエ変換である。が素数ならば formula_73 は有限体であり、単位元の原始乗根は が formula_80 を割り切るとき、つまり、ある正の整数 を用いて formula_81 と書けるときには、必ず存在する。特に、単位元の原始乗根が formula_82 であれば、原始乗根は formula_83 で得られる.
具体例）formula_84、formula_85、formula_86 の場合、
数論変換は、法が素数でない場合の環 formula_89 においても、位数がである主要根が存在するならば、意味がある。ショーンハーゲ・ストラッセン法で用いられるフェルマー数変換（）や、メルセンヌ数変換（）のような特殊な数論変換は、法として合成数を用いている。 
性質.
複素数上のDFTが持つ重要な特徴、例えば逆変換、畳み込み定理、多くの高速フーリエ変換(FFT) アルゴリズムなどは、変換の核が単位元の主要根であるという性質のみに依存している。したがって、一般化した離散フーリエ変換も同じ特徴を持つ（任意の環において、同様に証明できる）。特に、計算量が formula_90 の高速フーリエ変換アルゴリズムをNTTに適用できることと、畳み込み定理が成り立つことから、数論変換を利用することで、整数列の畳み込みを効率よく正確に計算できる。複素数上のDFTでも畳み込みを効率よく計算できるが、有限精度の浮動小数演算において丸め誤差が生じる恐れがある。一方NTTでは、固定サイズの整数しか扱わず、厳密に値を表現できるため、丸めの誤差は生じない。
高速なアルゴリズム.
高速なアルゴリズム実装のためには、（複素数上の離散フーリエ変換を計算する高速フーリエ変換アルゴリズムの場合と同様に）変換したい入力の長さ"n"は小さな素数から成る合成数（典型的なのは2の冪）が望ましいことが良くある。しかし、WangとZhuのアルゴリズムのように、有限体の場合に特化したフーリエ変換アルゴリズムも存在しており、それらは"n"の因数分解に寄らず効率が良い。