ショーンハーゲ・ストラッセン法
ショーンハーゲ・ストラッセン法は、大きな整数の掛け算を高速に計算できる乗算アルゴリズムである。1971年にアーノルド・ショーンハーゲとフォルカー・シュトラッセンによって発見された。2進法で "n "桁の整数同士の掛け算の時間計算量はランダウの記号を用いて formula_1 である。このアルゴリズムでは数論変換の1つである 2"n"+1個の要素を持つ整数環での高速フーリエ変換を用いる。
ショーンハーゲ・ストラッセン法は、発見された1971年から、フューラーのアルゴリズムが発見される2007年まで十分大きな整数の掛け算の最速アルゴリズムであった。しかし、ショーンハーゲ・ストラッセン法よりフューラーのアルゴリズムの性能が上回るのは天文学的に大きな整数同士の掛け算に限るため、フューラーのアルゴリズムはほとんど実用されていない。
実際には、ショーンハーゲ・ストラッセン法がカラツバ法やToom-3のような従来の手法より性能が上回り始めるのは、2215 - 2217（10進法で10 000 - 40 000桁）同士の掛け算である。GNU Multi-Precision Libraryはアーキテクチャに依存するが 、64ビット演算において少なくとも1728 - 7808ワード（10進法で33 000 - 150 000桁）の大きさの計算において初めてショーンハーゲ・ストラッセン法を用いる。10進法で74 000桁以上においてショーンハーゲ・ストラッセン法を用いるJavaの実装も存在する。
ショーンハーゲ・ストラッセン法の応用には、GIMPSや円周率の近似計算などの数学的経験主義や、整数係数多項式の乗算を整数の掛け算に帰着して効率的に行うクロネッカー置換などの実用的な応用がある。これは楕円曲線法のためにGMP-ECMで用いられている。