環上の離散フーリエ変換

Generalisation of Fourier transform to any ring

数学において、環上の離散フーリエ変換は、値が通常は複素数である関数の、任意の環上の離散フーリエ変換(DFT) を一般化したものです。

定義

Rを任意の環、を整数、を主n乗根とし、次のように定義されるものとする。^[1] ${\displaystyle n\geq 1}$ ${\displaystyle \alpha \in R}$

${\displaystyle {\begin{aligned}&\alpha ^{n}=1\\&\sum _{j=0}^{n-1}\alpha ^{jk}=0{\text{ for }}1\leq k<n\end{aligned}}}$

1

離散フーリエ変換は、Rのn個の要素の組 を、次の式に従ってRの別のn個の要素の組に写像します ${\displaystyle (v_{0},\ldots ,v_{n-1})}$ ${\displaystyle (f_{0},\ldots ,f_{n-1})}$

${\displaystyle f_{k}=\sum _{j=0}^{n-1}v_{j}\alpha ^{jk}.}$

2

慣例により、タプルは時間領域にあると言われ、インデックスjは時間と呼ばれます。タプルは周波数領域にあると言われ、インデックスkは周波数と呼ばれます。タプルはスペクトルとも呼ばれます。この用語は、信号処理におけるフーリエ変換の応用に由来しています ${\displaystyle (v_{0},\ldots ,v_{n-1})}$ ${\displaystyle (f_{0},\ldots ,f_{n-1})}$ ${\displaystyle (f_{0},\ldots ,f_{n-1})}$ ${\displaystyle (v_{0},\ldots ,v_{n-1})}$

Rが整域（体を含む）である場合、原始n乗根として1のn乗根を選択すれば十分であり、条件（1）は次のように置き換えられる：^[1] ${\displaystyle \alpha }$

${\displaystyle \alpha ^{k}\neq 1}$のために ${\displaystyle 1\leq k<n}$

証明

をとします。、 、 なので、 となります ${\displaystyle \beta =\alpha ^{k}}$ ${\displaystyle 1\leq k<n}$ ${\displaystyle \alpha ^{n}=1}$ ${\displaystyle \beta ^{n}=(\alpha ^{n})^{k}=1}$

${\displaystyle \beta ^{n}-1=(\beta -1)\left(\sum _{j=0}^{n-1}\beta ^{j}\right)=0}$

ここで、和は( 1 )と一致する。は原始根なので、Rは整域なので、和は0でなければならない。∎ ${\displaystyle \alpha }$ ${\displaystyle \beta -1\neq 0}$

nが2のべき乗の場合には、もう1つの簡単な条件が適用されます。( 1 )は に置き換えられます。^[1] ${\displaystyle \alpha ^{n/2}=-1}$

逆変換

離散フーリエ変換の逆変換は次のように与えられます

${\displaystyle v_{j}={\frac {1}{n}}\sum _{k=0}^{n-1}f_{k}\alpha ^{-jk}.}$

3

ここで、 Rにおけるnの逆数です（この逆数が存在しない場合、DFTは逆変換できません）。 ${\displaystyle 1/n}$

証明

（２ ）を（ ３）の右辺に代入すると、

${\displaystyle {\begin{aligned}&{\frac {1}{n}}\sum _{k=0}^{n-1}f_{k}\alpha ^{-jk}\\={}&{\frac {1}{n}}\sum _{k=0}^{n-1}\sum _{j'=0}^{n-1}v_{j'}\alpha ^{j'k}\alpha ^{-jk}\\={}&{\frac {1}{n}}\sum _{j'=0}^{n-1}v_{j'}\sum _{k=0}^{n-1}\alpha ^{(j'-j)k}.\end{aligned}}}$

これは と全く同じです。なぜなら 、 （1）で） のとき、 のとき、 だからです。∎ ${\displaystyle v_{j}}$ ${\displaystyle \sum _{k=0}^{n-1}\alpha ^{(j'-j)k}=0}$ ${\displaystyle j'\neq j}$ ${\displaystyle k=j'-j}$ ${\displaystyle \sum _{k=0}^{n-1}\alpha ^{(j'-j)k}=n}$ ${\displaystyle j'=j}$

行列の定式化

離散フーリエ変換は線形演算子なので、行列の乗算で記述できます。行列表記では、離散フーリエ変換は次のように表されます

${\displaystyle {\begin{bmatrix}f_{0}\\f_{1}\\\vdots \\f_{n-1}\end{bmatrix}}={\begin{bmatrix}1&1&1&\cdots &1\\1&\alpha &\alpha ^{2}&\cdots &\alpha ^{n-1}\\1&\alpha ^{2}&\alpha ^{4}&\cdots &\alpha ^{2(n-1)}\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&\alpha ^{n-1}&\alpha ^{2(n-1)}&\cdots &\alpha ^{(n-1)(n-1)}\\\end{bmatrix}}{\begin{bmatrix}v_{0}\\v_{1}\\\vdots \\v_{n-1}\end{bmatrix}}.}$

この変換の行列はDFT 行列と呼ばれます。

同様に、逆フーリエ変換の行列表記は

${\displaystyle {\begin{bmatrix}v_{0}\\v_{1}\\\vdots \\v_{n-1}\end{bmatrix}}={\frac {1}{n}}{\begin{bmatrix}1&1&1&\cdots &1\\1&\alpha ^{-1}&\alpha ^{-2}&\cdots &\alpha ^{-(n-1)}\\1&\alpha ^{-2}&\alpha ^{-4}&\cdots &\alpha ^{-2(n-1)}\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&\alpha ^{-(n-1)}&\alpha ^{-2(n-1)}&\cdots &\alpha ^{-(n-1)(n-1)}\end{bmatrix}}{\begin{bmatrix}f_{0}\\f_{1}\\\vdots \\f_{n-1}\end{bmatrix}}.}$

多項式の定式化

n組を形式多項式と同一視すると便利な場合があります ${\displaystyle (v_{0},\ldots ,v_{n-1})}$

${\displaystyle p_{v}(x)=v_{0}+v_{1}x+v_{2}x^{2}+\cdots +v_{n-1}x^{n-1}.\,}$

離散フーリエ変換の定義（2）の合計を書き出すと、次の式が得られます。

${\displaystyle f_{k}=v_{0}+v_{1}\alpha ^{k}+v_{2}\alpha ^{2k}+\cdots +v_{n-1}\alpha ^{(n-1)k}.\,}$

これは、が の多項式の値であることを意味します。つまり、 ${\displaystyle f_{k}}$ ${\displaystyle p_{v}(x)}$ ${\displaystyle x=\alpha ^{k}}$

${\displaystyle f_{k}=p_{v}(\alpha ^{k}).\,}$

4

したがって、フーリエ変換は多項式の係数と値を関連付けるものと見ることができます。係数は時間領域にあり、値は周波数領域にあります。ここで重要なのは、多項式がのn乗根、つまり のべき乗で評価されることです。 ${\displaystyle \alpha }$

同様に逆フーリエ変換（3）の定義は次のように書くことができる。

${\displaystyle v_{j}={\frac {1}{n}}(f_{0}+f_{1}\alpha ^{-j}+f_{2}\alpha ^{-2j}+\cdots +f_{n-1}\alpha ^{-(n-1)j}).}$

5

と

${\displaystyle p_{f}(x)=f_{0}+f_{1}x+f_{2}x^{2}+\cdots +f_{n-1}x^{n-1},}$

これは次のことを意味します

${\displaystyle v_{j}={\frac {1}{n}}p_{f}(\alpha ^{-j}).}$

これを次のようにまとめることができます。の値がの係数である場合、の値は、スカラー因子と並べ替えを除いて、の係数です。^[2] ${\displaystyle p_{v}(x)}$ ${\displaystyle p_{f}(x)}$ ${\displaystyle p_{f}(x)}$ ${\displaystyle p_{v}(x)}$

特殊なケース

複素数

が複素数体である場合、単位根は複素平面上の単位円上の点として視覚化できる。この場合、通常は次のように表される。 ${\displaystyle F={\mathbb {C} }}$ ${\displaystyle n}$

${\displaystyle \alpha =e^{\frac {-2\pi i}{n}},}$

これは複素離散フーリエ変換の通常の式を与える。

${\displaystyle f_{k}=\sum _{j=0}^{n-1}v_{j}e^{{\frac {-2\pi i}{n}}jk}.}$

複素数の場合、DFTと逆DFTの式を正規化する際に、DFTの式と逆DFTの式の両方でスカラー因子を用いるのではなく、両方の式でスカラー因子を用いるのが一般的です。この正規化により、DFT行列はユニタリ行列になります。ただし、任意の体では意味をなさないことに注意してください。 ${\displaystyle {\frac {1}{\sqrt {n}}}}$ ${\displaystyle 1}$ ${\displaystyle {\frac {1}{n}}}$ ${\displaystyle {\sqrt {n}}}$

有限体

が有限体で、qが素数冪である場合、原始n乗根の存在は自動的にnがを割り切ることを意味します。なぜなら、各元の乗法順序は、 Fの乗法群のサイズである を割り切れる必要があるからです。これは特に、 が逆であることを保証し、( 3 )の表記が意味を成します ${\displaystyle F=\mathrm {GF} (q)}$ ${\displaystyle q-1}$ ${\displaystyle q-1}$ ${\displaystyle n=\underbrace {1+1+\cdots +1} _{n\ {\rm {times}}}}$ ${\displaystyle {\frac {1}{n}}}$

離散フーリエ変換の応用として、符号理論におけるリード・ソロモン符号のBCH符号への縮約が挙げられます。このような変換は、適切な高速アルゴリズム、例えば円分高速フーリエ変換を用いることで効率的に実行できます。 ${\displaystyle \mathrm {GF} (q)}$

nを含まない多項式^番目根

と仮定します。もし の場合、 となる可能性があります。これは、に単位根を見つけることができないことを意味します。マシュケの定理に従って、フーリエ変換をいくつかの多項式に対する同型写像と見なすことができます。写像は中国剰余定理によって与えられ、逆写像は多項式に対するベズーの恒等式を適用することによって与えられます。^[3] ${\displaystyle F=\mathrm {GF} (p)}$ ${\displaystyle p\nmid n}$ ${\displaystyle n\nmid p-1}$ ${\displaystyle n^{th}}$ ${\displaystyle F}$ ${\displaystyle \mathrm {F} [C_{n}]=\mathrm {F} [x]/(x^{n}-1)\cong \bigoplus _{i}\mathrm {F} [x]/(P_{i}(x))}$ ${\displaystyle P_{i}(x)}$

${\displaystyle x^{n}-1=\prod _{d|n}\Phi _{d}(x)}$は円分多項式の積である。を因数分解することは、の素イデアルを因数分解することと同値である。 の位数である次数の多項式が得られる。 ${\displaystyle \Phi _{d}(x)}$ ${\displaystyle F[x]}$ ${\displaystyle (p)}$ ${\displaystyle \mathrm {Z} [\zeta ]=\mathrm {Z} [x]/(\Phi _{d}(x))}$ ${\displaystyle g}$ ${\displaystyle P_{1}\ldots P_{g}}$ ${\displaystyle f}$ ${\displaystyle fg=\varphi (d)}$ ${\displaystyle f}$ ${\displaystyle p{\text{ mod }}d}$

上で述べたように、 の基底体 を に拡張することで、 の原始根、つまりの分割体を求めることができます。 となるので、のそれぞれについて、要素はにマッピングされます。 ${\displaystyle \mathrm {GF} (q)}$ ${\displaystyle x^{n}-1}$ ${\displaystyle x^{n}-1=\prod _{k}(x-\alpha ^{k})}$ ${\displaystyle \sum _{j=0}^{n-1}v_{j}x^{j}\in F[x]/(x^{n}-1)}$ ${\displaystyle \sum _{j=0}^{n-1}v_{j}x^{j}\mod (x-\alpha ^{k})\equiv \sum _{j=0}^{n-1}v_{j}(\alpha ^{k})^{j}}$ ${\displaystyle k}$

pがnを割るとき

の場合でも、上記と同様に -線型同型を定義できます。ただし、 と であることに注意してください。上記の因数分解を に適用すると、分解 が得られます。ここで、発生する加群は既約ではなく分解不可能になります。 ${\displaystyle p|n}$ ${\displaystyle F_{p}}$ ${\displaystyle (x^{n}-1)=(x^{m}-1)^{p^{s}}}$ ${\displaystyle n=mp^{s}}$ ${\displaystyle p\nmid m}$ ${\displaystyle x^{m}-1}$ ${\displaystyle F[x]/(x^{n}-1)\cong \bigoplus _{i}F[x]/(P_{i}(x)^{p^{s}})}$

DFT行列の順序

と仮定すると、 1の根を持つ。を上記のDFT行列、つまり を要素とするヴァンデルモンド行列とする。の場合、すべての要素が1になることを思い出してください。の場合、公比 を持つ等比級数となるため、 が得られる。分子は0だが、の場合、分母は0ではない。 ${\displaystyle p\nmid n}$ ${\displaystyle n^{th}}$ ${\displaystyle \alpha }$ ${\displaystyle A}$ ${\displaystyle A_{ij}=\alpha ^{ij}}$ ${\displaystyle 0\leq i,j<n}$ ${\displaystyle \sum _{j=0}^{n-1}\alpha ^{(k-l)j}=n\delta _{k,l}}$ ${\displaystyle k=l}$ ${\displaystyle k\neq l}$ ${\displaystyle \alpha ^{k-l}}$ ${\displaystyle {\frac {1-\alpha ^{n(k-l)}}{1-\alpha ^{k-l}}}}$ ${\displaystyle \alpha ^{n}=1}$ ${\displaystyle k-l\neq 0}$

まず平方根を計算します。同様に計算し、デルタを簡略化すると、 が得られます。したがって、となり、順序は です。 ${\displaystyle (A^{2})_{ik}=\sum _{j=0}^{n-1}\alpha ^{j(i+k)}=n\delta _{i,-k}}$ ${\displaystyle A^{4}=(A^{2})^{2}}$ ${\displaystyle (A^{4})_{ik}=n^{2}\delta _{i,k}}$ ${\displaystyle A^{4}=n^{2}I_{n}}$ ${\displaystyle 4\cdot {\text{ord}}(n^{2})}$

DFT行列の正規化

複素数の場合と整合させ、行列が正確に4次であることを保証するため、上記のDFT行列を で正規化することができます。の分解体には は存在しないかもしれませんが、平方根が存在する二次拡張を形成できることに留意してください。そして、 、 と設定します。 ${\displaystyle A}$ ${\displaystyle {\frac {1}{\sqrt {n}}}}$ ${\displaystyle {\sqrt {n}}}$ ${\displaystyle F_{q}}$ ${\displaystyle x^{n}-1}$ ${\displaystyle F_{q^{2}}\cong F_{q}[x]/(x^{2}-n)}$ ${\displaystyle U={\frac {1}{\sqrt {n}}}A}$ ${\displaystyle U^{4}=I_{n}}$

ユニタリー性

と仮定します。DFT行列が有限体 上でユニタリーであるかどうかを問うことができます。行列の要素が 上にある場合、 が完全な平方数であることを確認するか、 2次の自己同型性 を定義するために まで拡張する必要があります。上記のDFT行列 を考えます。 が対称であることに注意してください。共役と転置を行うと が得られます ${\displaystyle p\nmid n}$ ${\displaystyle F_{q}}$ ${\displaystyle q}$ ${\displaystyle F_{q^{2}}}$ ${\displaystyle x\mapsto x^{q}}$ ${\displaystyle A_{ij}=\alpha ^{ij}}$ ${\displaystyle A}$ ${\displaystyle A_{ij}^{*}=\alpha ^{qji}}$

${\displaystyle (AA^{*})_{ik}=\sum _{j=0}^{n-1}\alpha ^{j(i+qk)}=n\delta _{i,-qk}}$

上記と同様の等比級数の議論によって、 は正規化によって除去でき、と となる。したがって、 は のときのみユニタリとなる。単位根 が存在するので、であることを思い出してください。これは を意味する。が最初から完全な平方数でない場合は となり、となることに注意。 ${\displaystyle n}$ ${\displaystyle U={\frac {1}{\sqrt {n}}}A}$ ${\displaystyle (UU^{*})_{ik}=\delta _{i,-qk}}$ ${\displaystyle U}$ ${\displaystyle q\equiv -1\,({\text{mod}}\,n)}$ ${\displaystyle n^{th}}$ ${\displaystyle n|q^{2}-1}$ ${\displaystyle q^{2}-1\equiv (q+1)(q-1)\equiv 0\,({\text{mod}}\,n)}$ ${\displaystyle q}$ ${\displaystyle n|q-1}$ ${\displaystyle q\equiv 1\,({\text{mod}}\,n)}$

たとえば、 を5 乗根に拡張する必要がある場合などです。 ${\displaystyle p=3,n=5}$ ${\displaystyle q^{2}=3^{4}}$ ${\displaystyle q=9\equiv -1\,({\text{mod}}\,5)}$

非例として、を 8 乗根に拡張して1 の 8 乗根を得る場合、 となり、この場合は となり、 となります。は単位元の平方根であるため、 は1 乗ではありません。 ${\displaystyle p=3,n=8}$ ${\displaystyle F_{3^{2}}}$ ${\displaystyle q^{2}=9}$ ${\displaystyle q\equiv 3\,({\text{mod}}\,8)}$ ${\displaystyle q+1\not \equiv 0}$ ${\displaystyle q-1\not \equiv 0}$ ${\displaystyle UU^{*}}$ ${\displaystyle U}$

DFT行列の固有値

のとき、分解体 に単位根があります。上記のDFT行列の特性多項式は で分解できない可能性があることに注意してください。DFT行列は4次です。DFT行列の特性多項式の分解拡張、つまり少なくとも単位根の4乗根を含むDFT行列のさらなる拡張 を行う必要があるかもしれません。が の乗法群の生成元である場合、複素数の場合と全く同様に、固有値は です。それらは、ある非負の重複度で発生します。 ${\displaystyle p\nmid n}$ ${\displaystyle n^{th}}$ ${\displaystyle \alpha }$ ${\displaystyle F_{q}\cong F_{p}[x]/(x^{n}-1)}$ ${\displaystyle F_{q}}$ ${\displaystyle F_{q'}}$ ${\displaystyle a}$ ${\displaystyle F_{q'}}$ ${\displaystyle \{\pm 1,\pm a^{(q'-1)/4}\}}$

数論的変換

数論的変換（NTT）^[4]は、離散フーリエ変換を素数pを法とする整数に特殊化することで得られます。これは有限体であり、nがpを割り切るときは常に原始n乗根が存在するため、正の整数ξに対して次が成り立ちます。具体的には、を原始n乗根とすると、n乗根はとすることで求められます ${\displaystyle F={\mathbb {Z} }/p}$ ${\displaystyle p-1}$ ${\displaystyle p=\xi n+1}$ ${\displaystyle \omega }$ ${\displaystyle (p-1)}$ ${\displaystyle \alpha }$ ${\displaystyle \alpha =\omega ^{\xi }}$

例えば、 ${\displaystyle p=5}$ ${\displaystyle \alpha =2}$

${\displaystyle {\begin{aligned}2^{1}&=2{\pmod {5}}\\2^{2}&=4{\pmod {5}}\\2^{3}&=3{\pmod {5}}\\2^{4}&=1{\pmod {5}}\end{aligned}}}$

とき ${\displaystyle N=4}$

${\displaystyle {\begin{bmatrix}F(0)\\F(1)\\F(2)\\F(3)\end{bmatrix}}={\begin{bmatrix}1&1&1&1\\1&2&4&3\\1&4&1&4\\1&3&4&2\end{bmatrix}}{\begin{bmatrix}f(0)\\f(1)\\f(2)\\f(3)\end{bmatrix}}}$

環において、法 mが素数でなくても、 n位の主根が存在する限り、数論的変換は意味を持つことがあります。シェーンハーゲ・シュトラッセンアルゴリズムで使用されるフェルマー数変換（m = 2 ^k + 1）やメルセンヌ数変換^[5]（m = 2 ^k  − 1）などの数論的変換の特殊なケースでは、合成法が使用されます ${\displaystyle \mathbb {Z} /m}$

一般に、 ならば、 を法とする単位根を求めることで、 を法とする単位根を求めることができ、組が得られる。中国剰余定理同型のもとでのの逆像は、となる単位根である。これにより、上記の和の条件が満たされることが保証される。各 に対して が成り立つことが必要である。ここではオイラーのトーティエント関数である。^[6] ${\textstyle m=\prod _{i}p_{i}^{e_{i}}}$ ${\textstyle n^{th}}$ ${\textstyle n^{th}}$ ${\displaystyle g_{i}}$ ${\textstyle p_{i}^{e_{i}}}$ ${\textstyle g=\left(g_{i}\right)_{i}\in \prod _{i}\left(\mathbb {Z} /p_{i}^{e_{i}}\mathbb {Z} \right)^{\ast }}$ ${\displaystyle g}$ ${\textstyle n^{th}}$ ${\textstyle \alpha }$ ${\textstyle \alpha ^{n/2}=-1\mod m}$ ${\textstyle n|\varphi (p_{i}^{e_{i}})}$ ${\displaystyle i}$ ${\displaystyle \varphi }$

高速フーリエ変換はNTTに適応でき、整数演算のみで実装できる。^[7]ソリナス素数のようなmの選択は、減算に除算演算を必要としないため、コンピュータ上で計算するのがさらに簡単である。^[8] ${\displaystyle 2^{64}-2^{32}+1}$

離散重み付け変換

離散加重変換（DWT）は、任意の環上の離散フーリエ変換のバリエーションであり、入力を重みベクトルで要素ごとに乗算して変換し、その結果を別のベクトルで重み付けする。[ ^9]無理数基底離散加重変換は、この特殊なケースである。

性質

逆変換、畳み込み定理、およびほとんどの高速フーリエ変換（FFT）アルゴリズムを含む複素DFTの重要な属性のほとんどは、変換の核が主根であるという性質のみに依存します。これらの性質は、任意の環上でも同一の証明で成り立ちます。体の場合、この類推は1つの元を持つ体によって形式化でき、 n乗原始根を持つ任意の体を拡大体上の代数と見なすことができます^{[説明が必要]} ${\displaystyle \mathbf {F} _{1^{n}}.}$

特に、NTTの計算に高速フーリエ変換アルゴリズムを適用できることと、畳み込み定理を組み合わせることで、数論的変換は整数列の正確な畳み込みを効率的に計算できる方法となります。複素DFTでも同じタスクを実行できますが、有限精度浮動小数点演算では丸め誤差の影響を受けます。NTTは、正確に表現できる固定サイズの整数のみを扱うため、丸め誤差は発生しません。 ${\displaystyle O(n\log n)}$

高速アルゴリズム

「高速」アルゴリズム（FFTがDFTを計算する方法に似ています）を実装するには、変換長も高度に合成された（例えば2のべき乗）ことが望ましい場合がよくあります。しかし、WangとZhuのアルゴリズム^[10]など、変換長の係数に関係なく効率的な、有限体用の特殊な高速フーリエ変換アルゴリズムがあります

参照

• 離散フーリエ変換（複素数）
• 有限群上のフーリエ変換
• ガウス和
• 畳み込み
• 最小二乗スペクトル解析
• 乗算アルゴリズム

参考文献

1. Martin Fürer、「高速整数乗算」、STOC 2007 Proceedings、pp. 57–66。第2章：離散フーリエ変換
2. R. LidlとG. Pilz. 応用抽象代数第2版. Wiley, 1999, pp. 217–219.
3. "Jacksonwalters/DFT-finite-groups". GitHub .
4. Agarwal, R.; Burrus, C. (1974年4月). 「フェルマー数変換を用いた高速畳み込みとデジタルフィルタリングへの応用」. IEEE Transactions on Acoustics, Speech, and Signal Processing . 22 (2): 87– 97. doi :10.1109/TASSP.1974.1162555. ISSN  0096-3518.
5. Rader, CM (1972年12月). 「メルセンヌ変換による離散畳み込み」. IEEE Transactions on Computers . C-21 (12): 1269– 1273. doi :10.1109/TC.1972.223497. ISSN  0018-9340. S2CID  1939809.
6. Walters, Jackson; Silverman, Thomas. "ntt". crates.io . 2025年2月14日閲覧。
7. Satriawan, Ardianto; Syafalni, Infall; Mareta, Rella; Anshori, Isa; Shalannanda, Wervyan; Barra, Aleams (2023). 「数論的変換の概念的レビューとその実装に関する包括的レビュー」. IEEE Access . 11 : 70288–70316 . doi : 10.1109/ACCESS.2023.3294446 .
8. Craig-Wood, Nick. 「整数DWT mod 2^64-2^32+1」www.craig-wood.com .
9. Crandall, Richard; Fagin, Barry (1994)、「離散重み付け変換と大整数演算」(PDF)、Mathematics of Computation、62 (205): 305– 324、doi : 10.2307/2153411、JSTOR  2153411
10. Yao WangとXuelong Zhu、「有限体上のフーリエ変換の高速アルゴリズムとそのVLSI実装」、IEEE Journal on Selected Areas in Communications 6(3)572–577、1988年

外部リンク

• https://www.apfloat.org/ntt.html

Retrieved from "https://en.wikipedia.org/w/index.php?title=Discrete_Fourier_transform_over_a_ring&oldid=1323661615"