ショーンハーゲ・ストラッセン法
ショーンハーゲ・ストラッセン法の鍵となる洞察は法 N の選択であり、ある整数 n を用いてN=2 + 1であるものを選ぶ。 ここで n は変換を受けるブロックの数 P=2 の倍数である。このことから大きな整数を二進表現する標準的なシステムにおいては以下のような多くの利点が生じる:
任意の整数を法 2 + 1 で合同な数に還元することは、シフト演算と加算演算だけでできる。
環における全ての1の冪根は、 2 のかたちになる。そのことから、任意の数の1の冪根による乗算や除算は二進数のシフト演算になり、1の冪根の累乗や平方の計算は冪指数についての計算だけでできる。
変換された2つのベクトルの間の要素ごとの積の再帰的な計算は、逆向きの巡回畳み込みによってできる。この計算は線形畳み込みよりも高速であり、 mod (2 + 1 )での結果の還元は既にできているので手間が省ける。
再帰的な乗算の実行を便利に行うためには、ショーンハーゲ・ストラッセン法を、2つの整数の積を計算するだけではなくて、与えられた n に対するmod ( 2 + 1) での2つの整数の積の計算を行うものとして組み立てる。これによって一般性を失うことはない、なぜならば n を十分大きく選べば、mod(2 + 1 )での積が単に2つの整数の積となるようにできるからである。
ショーンハーゲ・ストラッセン法も、他の高速フーリエ変換を用いる乗算と同じように、畳み込み定理の巡回畳み込みを効率的に計算できる性質を用いている。具体的には、
2つのベクトルの巡回畳み込みは、それぞれを一度離散フーリエ変換し、その結果の積を逆離散フーリエ変換することで得られる。
数式で表現すると(ここでのドット積はベクトルの内積(スカラー積)ではなくて、2つのベクトルを成分ごとに積を作って新しいベクトルを作る操作である)
CyclicConvolution(X, Y) = IDFT(DFT(X) · DFT(Y))
入力を変換した DFT(X) と DFT(Y) の積を計算するためにも高速フーリエ変換を用いて離散フーリエ変換と逆離散フーリエ変換を行い、乗算アルゴリズムを再帰的に呼び出すことで、巡回畳み込みを効率的に計算できる。
このアルゴリズムは、逆向きの巡回畳み込みを用いれば重みの付いた変換である DWT に対応する畳み込み定理も適用でき、より有用なアルゴリズムとなる。ベクトル X と Y の長さが n であり、 aが 位数 2n の原始根であるとする(つまり、a = 1 )。このとき、Aを重みベクトルとして以下のように定義する
A = (a), 0 ≤ j < n
A = (a), 0 ≤ j< n
よって、
NegacyclicConvolution(X, Y) = A · IDFT(DFT(A · X) · DFT(A · Y))
といえる。離散フーリエ変換前にAが掛けられ、逆離散フーリエ変換後にAが掛けられることを除けばほぼ同じ形である。