「高速乗算法の設計と実装(1)」(→[N6])においては素体F_p上の離散フーリエ変換について考えたが、ここでは一般の有限体上の離散フーリエ変換について考える。

　1の原始n乗根ζ_nが存在する場合に条件3について考える。が可換環であるという条件だけで成立するが、ここで1≠ζ_n^kであるから、すべてのkについて(1-ζ_n^k)が単元であるとき条件3が満たされることがわかる。体上ではこの条件はつねに満たされる。

　定理の形でまとめると次のようになる。

　メルセンヌ素数、すなわち、の形の素数について考える。平方剰余の第１補充法則よりであるから、-1はpを法として平方非剰余である。したがってF_p上の多項式x²+1は既約であり、剰余環F_p[x]/(x²+1)はF_p上２次の拡大体となる。これはガウスの複素整数Z[i], i²=-1をイデアル(p)で剰余したZ_p[i]と体として同型である。Z_p[i]の元は、と表現することができ、加算と乗算はという式で計算することができる。

　定理1.2により、Z_p[i]を係数体としたとき、長さnの離散フーリエ変換が存在するための必要十分条件は、である。

　メルセンヌ素数M₃₁=2³¹-1を法とする剰余演算は、32ビット算術演算器で効率よく処理することができる。高速乗算法(2)はこの性質を利用して実装される。離散フーリエ変換の長さnとしてなるものが使用できるので当面の目的には十分である。

　p=M₃₁とし、Z_p[i]上の離散フーリエ変換を行なうにあたってその原始根を求めなければならない。一般に大きい有限体の原始根を探索することは計算量が多く難しい問題であるが、この場合は、原始根探索プログラムによって比較的簡単に原始根を発見することができた。

　離散フーリエ変換の長さNとしてはという形のものを使うことにする。このNは離散フーリエ変換の条件を満たし、さらに原始根12+iを使って1の原始N乗根をと表現することができる。

Step 1. 数のP進表現
　基数をP=2³²とし、長さをとする。正の整数a,bが次のようにP進表現されるものとする。この積について0≦ab＜P^Nが成り立つと仮定する。

Step 2. 多項式としての積の計算
　P^K≡1(mod P^N-1)より、となる。この係数c_r=��_{s+t≡r(mod N)}a_sb_tの大きさを評価すると、となる。

Step 3. 係数の分解
　２つの不等式より、係数c_rをによって評価する。係数をM₃₁を法とした場合とT₅を法とした場合の２つに分解する。

Step 4. 離散フーリエ変換による係数の計算
　c'_rは、(N, Z_M31[i], ω), ω=(12+i)^t, t=2^32-n(2³⁰-1)型の離散Fourier変換を利用して次のように計算する。c''_rは、(N, F_T5, ζ), ζ=7^t, t=2^32-n(2³²-1)型の離散Fourier変換を利用して次のように計算する。

Step 5. 孫子の剰余定理による連立方程式の解法
　(M₃₁, T₅)=1であるから、孫子の剰余定理からc_rを、連立合同式を解くことによって求めることができる。

Step 6. 桁上げ処理
　最後にc_r, r=0,…,K-1に桁上げ処理を施すことで、c=abのP進表現が得られる。