ショーンハーゲ-ストラッセン法の概略を少し改良した形で述べ、その全体構造を俯瞰する。

数のP進表現と積の評価
　K=2^k(k＞0), N=2^Kとし、正の整数a,bが基数P=2^Kにより次のようにP進表現されるものとする。この場合0≦a,b≦2^N-1であるが、この積について0≦ab≦2^N-1となるようにNを定める。このときabは2^N-1を法として求めればよい。

多項式としての積とその係数の評価
　P^K≡1(mod 2^N-1)より、となる。この係数c_r=��_{s+t≡r(mod K)}a_sb_tの大きさを評価すると、となる。したがってc_rはK(2^2K+1)を法として求めればよい。

孫子の剰余定理による係数の計算
(K, 2^2K+1)=1であるから、孫子の剰余定理からc_rを、c'_r及びc''_rが既知であるとして、連立合同式を解くことによって求めることができる。

離散フーリエ変換による係数の計算
　c'_rは直接計算し、c''_rは、(K, 2^2K+1, 2⁴)型の離散Fourier変換を利用して次のように計算する。

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

　ショーンハーゲ-ストラッセン法の構造からわかることは、高速乗算法が次のような乗算変換を組み合わせてできあがっているということである。(→[N5],[D2],[D3])

　ショーンハーゲ-ストラッセン法を構成する乗算変換を列挙してみる。

乗算変換１
　自然な準同型写像による乗算変換

乗算変換２
　自然な準同型写像による乗算変換

乗算変換３
　孫子の剰余定理による同型写像による乗算変換

乗算変換４
　G={ζⁱ|i=0,1,…K-1}としたとき離散フーリエ変換の構造定理(→[N3])による同型写像による乗算変換

　ショーンハーゲ-ストラッセン法が４つの乗算変換に分解することができるということをみたが、すべての高速乗算法はこのような乗算変換へ分解できることがわかっている。(→[N5])

　高速乗算法が乗算変換へ分解できるという性質を意識することによって、全体の見通しがよくなると同時に、部品となる乗算変換をいくつか用意して、それらをうまく組み合わせることによって高速乗算法を組み立てていくという設計法が可能になる。

　ショーンハーゲ-ストラッセン法を変形して、実際に高速乗算法を設計することについて考えてみる。まず多倍長整数を計算機の内部でどのように表現するかであるが、これは現在の計算機の多くが8=2³bitの倍数の長さの２進算術演算器をもっているということから、P=2^K, K=2^k(k＞0)としてP進表現するとしてよいであろう。ションハーゲ-ストラッセン法においては長さNとKにはN=2^Kという関係があったが、これは理論上の計算量を最小にするための工夫であって、このままでは実用には適さない。実際にはこの関係をもっと自由度の高いものにしなければならない。

とするとき積abを2^N-1を法として計算するととなる。この係数c_r=��_{s+t≡r(mod N)}a_sb_tの大きさを評価すると、となる。この右側の評価式c_r ≦ N(2^K-1)²を変形して、右辺が孫子の剰余定理でうまく分解できるようにすることが設計の第１段階である。

　長さNのFFT算法を用意することが設計の第２段階である。このNの選択にあたっては離散フーリエ変換の条件を満たさなければならないという制約がある。この制約は第１段階とも関係し、また1の原始N乗根の値が計算しやすい形かどうかということも検討すべき項目である。

　次節以降、

1. 適当な素数pを探して、係数の評価式としてc_r ＜ Npが成り立つようにする。
2. N=2ⁿ, n＞0であるとし、FFT算法としてCooley-Tukey型算法を使用する。

という方針で高速乗算法を設計し、そのPentiumへ実装法について検討する。

　我々はすでに可換環上で離散フーリエ変換を定義し、その諸性質をまとめている。(→[N3]) 工学分野では整数の剰余環上で定義された離散フーリエ変換のことを数論変換(NTT, Number Theoretic Transform)と呼ぶことがある。(→[S3],[D1])

　ここでは法mと長さnが与えられたとき、離散フーリエ変換が定義できるための条件について考える。長さの逆元が存在することは(n,m)=1と同値である。法mが素数のとき、1の原始n乗根の存在については次のことがいえる。

　法mが合成数のときも既約剰余類群(Z/mZ)^*の構造を考えれば、1の原始n乗根の存在する条件がわかる。

　離散フーリエ変換の1の原始n乗根ζが存在する場合に条件3について考える。が可換環であるという条件だけで成立するが、ここで1≠ζ^kであるから、すべてのkについて(1-ζ^k)が単元、すなわちのとき条件3が満たされることがわかる。法mが素数のとき、この条件はつねに満たされる。

　以下、素数pを法とする場合についてのみ考える。この場合剰余環Z/pZは有限体F_pとなる。この単元群(F_p)^*は位数p-1の巡回群であり、その生成元rはpを法とする原始根と呼ばれる。n|p-1なることと1の原始n乗根ζが存在することは同値であり、と表現される。原始根は一意的には定まらないのでこの表現も一意的ではない。上で示したようにF_pにおいては1の原始n乗根ζが存在すれば(n,p,ζ)は離散フーリエ変換の条件を満たす。これを定理の形で整理しておく。

　係数の評価式c_r ＜ Npにおける素数pを探す。が成り立っているので、なる素数pであって、F_pの演算、すなわち法pの剰余演算が高速に計算できるものを探さなければならない。我々はションハーゲ-ストラッセン法の実装実験(→[N4])において、数論変換を使う高速乗算法は、剰余演算が高速実行できなければ実用にはならないということをすでに経験している。

とおくとが成り立つ。T(n),n=0,1,2,3,4,5,6を素数判定してみる。T(5)、すなわちK=2⁵=32の場合に素数になっているが、これは32bitアーキテクチャのCPUには大変都合がよい。各係数はと表現できるが、このとき、より除算を使わずに剰余演算ができる。(→[S5])

　p = T(5) = 2³²(2³²-1)+1とする。これは素数であり、という係数の評価式が成り立つ。さらにF_p上に長さNの離散フーリエ変換が存在するための必要十分条件は、であるが、はこの条件を満たし、さらにこのときpの最小原始根7を使ってF_p上の1の原始N乗根をと表現することができる。