Schönhage-Strassen-Algorithmus

Der Schönhage-Strassen-Algorithmus ist ein Algorithmus zur Multiplikation zweier n-stelliger ganzer Zahlen. Er wurde 1971 von Arnold Schönhage und Volker Strassen entwickelt. Der Algorithmus basiert auf einer sehr schnellen Variante der diskreten schnellen Fourier-Transformation sowie einem geschickten Wechsel zwischen der Restklassen- und der zyklischen Arithmetik in endlichen Zahlenringen.

Der Schönhage-Strassen-Algorithmus terminiert in ${\displaystyle O{\Big (}n\cdot \log(n)\cdot \log {\big (}\log(n){\big )}{\Big )}}$ (siehe Landau-Notation), wenn als Effizienzmaß die Bitkomplexität auf mehrbändigen Turingmaschinen, also die maximale Laufzeit des Algorithmus gemessen als benötigte Bitoperationen in Abhängigkeit von der Bitlänge ${\displaystyle n}$ der Eingabegrößen gewählt wird. Diese Komplexität stellt eine Verbesserung sowohl gegenüber dem naiven aus der Schule bekannten Algorithmus der Laufzeit ${\displaystyle O\left(n^{2}\right)}$ als auch gegenüber dem 1962 entwickelten Karatsuba-Algorithmus mit einer Laufzeit von ${\displaystyle O\left(n^{\log _{2}(3)}\right)}$ sowie dessen verbesserter Variante, dem Toom-Cook-Algorithmus mit ${\displaystyle O(n^{1+\varepsilon })}$ Laufzeit dar.

Der Schönhage-Strassen-Algorithmus war von 1971 bis 2007 der effizienteste bekannte Algorithmus zur Multiplikation großer Zahlen; 2007 veröffentlichte Martin Fürer eine Weiterentwicklung des Algorithmus mit der noch niedrigeren asymptotischen Komplexität ${\displaystyle n\cdot \log(n)\cdot 2^{O(\log ^{*}(n))}}$, wobei ${\displaystyle \log ^{*}(n)}$ der iterierte Logarithmus von n ist. Durch Optimierungen des Algorithmus von Fürer erreichten David Harvey, Joris van der Hoeven und Grégoire Lecerf 2014 eine Verbesserung der asymptotischen Laufzeit auf ${\displaystyle O(n\cdot \log(n)\cdot 2^{3\log ^{*}(n)})}$. Harvey und van der Hoeven stellten 2021 schließlich einen weiteren Algorithmus vor, der die von Schönhage und Strassen postulierte Laufzeit von ${\displaystyle O(n\cdot \log(n))}$ erreicht.