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 (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 der Eingabegrößen gewählt wird.Diese Komplexität stellt eine Verbesserung sowohl gegenüber dem naiven aus der Schule bekannten Algorithmus der Laufzeit als auch gegenüber dem 1962 entwickelten Karatsuba-Algorithmus mit einer Laufzeit von sowie dessen verbesserter Variante, dem Toom-Cook-Algorithmus mit Laufzeit dar. Der Schönhage-Strassen-Algorithmus war von 1971 bis 2007 der effizienteste bekannte Algorithmus zur Multiplikation großer Zahlen; 2007 veröffentlichte eine Weiterentwicklung des Algorithmus mit der noch niedrigeren asymptotischen Komplexität , wobei der iterierte Logarithmus von n ist.Durch Optimierungen des Algorithmus von Fürer erreichten David Harvey, Joris van der Hoeven und Grégoire Lecerf eine weitere Verbesserung der asymptotischen Laufzeit auf .