ショーンハーゲ・ストラッセン法
このアルゴリズムはカラツバ法やToom-3と同様に、分割・評価(高速フーリエ変換)・アダマール積・補間(逆高速フーリエ変換)・結合の順に行われる。
入力である x と y 、そして整数 N が与えられれば、次のアルゴリズムは xy mod 2 + 1 を計算する。N が充分大きい場合、単に xy である。
それぞれの入力を 2 個の部分に分割し、X と Y とする。(e.g. 12345678 → (12, 34, 56, 78))
再帰的な乗算のために、小さな N を用意する。そのために、2N/2 + k 以上で 2 で割り切れる最小の整数を n とする。
逆向きの巡回畳み込みによって、mod 2 + 1 における X と Y の積を計算する シフト演算を用いて、X と Y に重みベクトル A を乗ずる。 数論変換高速フーリエ変換を用いてXとYの離散フーリエ変換を計算する。ここで、全ての乗算はシフト演算で行われる。 再帰的にこのアルゴリズムを適用して、変換後の X と Y の要素を掛ける(ドット積)。 3.