ショーンハーゲ・ストラッセン法
B 進法において、繰り上がりを無視し123 × 456を筆算する場合、以下のようになる。
こうして計算された最下部の数列 (4, 13, 28, 27, 18) を (1,2,3)と(4,5,6) の線形畳み込みもしくは直線畳み込みと呼ぶ。2つの数列の線形畳み込みが計算できれば、元の数の積の計算は単に繰り上がりを実行するだけで容易であり、例えば上の例では右端の8を保持したまま1を27に加算するなどの作業を繰り返すだけである。この例では、繰り上がりを実行することで123 × 456 の積 56088 が得られる。
他にも、便利な畳込みが2種類存在する。入力する数列がn要素である場合の(ここでは n=3)線形畳み込みを考える。上の例の(繰り上がり処理をする前の5つの要素について)右端からn要素を左端からn-1要素に足す。これが巡回畳み込み(cyclic convolution)である。
離散フーリエ変換は、任意の代数環で実行できる抽象的な概念である。一般的には複素数において計算されるが、乗算の正確な結果を保証するため十分に高い精度で計算することは複雑な処理が必要になり、実行速度は遅くなる。ここではその代わりに、数論変換を行い、整数 N を用いて mod N において変換を実行する。
複素平面内にすべての1の冪根とその冪乗が存在するのと同じように、与えられた任意の位数 n に対して、うまく整数 N を選んで b が法 N における1の原始根となるようにできる (つまり、b ≡ 1 (mod N) であり、かつ b の冪乗で指数が正でかつ n 未満のものはどれも mod N で 1 と合同にならない。)
このアルゴリズムは、小さな数値の再帰的な乗算にほとんどの時間を費やす。それは素朴な実装では、以下のように多くの場所で発生する。
高速フーリエ変換において、原始根 b は繰り返して、累乗・自乗・(他の値との)乗算がされる。
重みベクトル A か逆の重みベクトル A を他のベクトルに掛けるときには、重みベクトル A を形成するために原始根 a の累乗が計算される。
変換された2つのベクトルの間の成分ごとの積の計算。