Karatsuba-Algorithmus

Der Karazuba-Algorithmus ist ein Algorithmus zur Multiplikation zweier großer ganzer Zahlen. Er wurde 1960 von dem 23-jährigen Anatoli Alexejewitsch Karazuba (engl. Karatsuba, russisch Анатолий Алексеевич Карацуба) entwickelt und 1962 veröffentlicht. Bezeichnet die Bit-Anzahl der beiden Zahlen und ein Landau-Symbol, so ist der Algorithmus mit einer Laufzeitkomplexität von deutlich schneller als die Schulmethode. Diese (und auch deren implizite Übertragung auf das Binärsystem in Form der russischen Bauernmultiplikation) besitzt eine Laufzeitkomplexität von . Die Methode von Karazuba wurde zum Vorbild für das Teile-und-herrsche-Prinzip in der Informatik. Für hinreichend große Zahlen ist der Karazuba-Algorithmus langsamer als seine Verallgemeinerungen, wie der Toom-Cook-Algorithmus (1965) und der Schönhage-Strassen-Algorithmus (1971), dessen Laufzeitkomplexität beträgt und der aus Sicht der Komplexitätstheorie als schnellster Algorithmus zur Multiplikation großer ganzer Zahlen galt, bis 2007 eine Weiterentwicklung mit einer (bisher nur theoretisch) geringeren Laufzeitkomplexität vorstellte.