Ein fast 50 Jahre altes mathematisches Rätsel rund um die Multiplikation ist gelöst: Die Mathematiker David Harvey von der University of New South Wales und Joris van der Hoeven von der École Polytechnique nahe Paris haben vermutlich den schnellsten möglichen Algorithmus zum Multiplizieren ganzer Zahlen mit gleich vielen Stellen entwickelt – und vor allem bewiesen, dass kein schnellerer möglich ist. Ihr Verfahren benötigt lediglich n · log(n) Einzeloperationen dazu, wobei n die Zahl der Dezimalstellen der Zahlen ist. Die Arbeit ist im (anders als der Name nahelegt) offenen Preprint-Archiv »HAL« veröffentlicht, eine Überprüfung des Beweises steht jedoch noch aus.

Bereits 1971 vermuteten Arnold Schönhage und Volker Strassen, dass dies die Mindestzahl an Operationen ist, wenn man zwei derartige ganze Zahlen multipliziert. Beim klassischen schriftlichen Multiplizieren nimmt man eine Zahl nacheinander mit jeder einzelnen Stelle der zweiten Zahl mal und addiert schließlich die Zwischenergebnisse. Allerdings steigt bei diesem Algorithmus die dafür nötige Zeit mit dem Quadrat der Anzahl der Stellen an – was bei sehr langen Zahlen auch für schnelle Computer zu Problemen führt. Schönhage und Strassen sowie Forscher nach ihnen entwickelten schnellere Algorithmen, ohne jedoch das theoretische Limit zu erreichen. Das scheinen Harvey und van der Hoeven nun geschafft zu haben. Aber die Sache hat derzeit noch einen kleinen Haken: Ihr Algorithmus ist nur bei unfassbar großen Zahlen tatsächlich schneller als die bisherigen Methoden. Also ist es vorerst unwahrscheinlich, dass er jemals praktische Bedeutung hat.