De vermenigvuldiging van gehele getallen is een probleem dat wiskundigen al sinds de oudheid bezighoudt. De "Babylonische" methode die we op school leren, vereist dat we elk cijfer van het eerste getal vermenigvuldigen met elk cijfer van het tweede. Maar als beide getallen elk een miljard cijfers hebben, dat betekent een miljard keer een miljard of 10 ¹⁸ activiteiten.

Met een snelheid van een miljard handelingen per seconde, een computer zou iets meer dan 30 jaar nodig hebben om de klus te klaren. 1971, de wiskundigen Schönhage en Strassen ontdekten een snellere manier, rekentijd terugbrengen tot ongeveer 30 seconden op een moderne laptop. In hun artikel, ze voorspelden ook dat een ander algoritme - dat nog moet worden gevonden - het nog sneller zou kunnen doen. Joris van der Hoeven, een CNRS-onderzoeker van het École Polytechnique Computer Science Laboratory LIX, en David Harvey van de University of New South Wales (Australië) hebben dat algoritme gevonden.

Ze presenteren hun werk in een nieuw artikel dat beschikbaar is voor de wetenschappelijke gemeenschap via het online HAL-archief. Maar één probleem dat door Schönhage et Strassen naar voren is gebracht, moet nog worden opgelost:bewijzen dat er geen snellere methode bestaat. Dit vormt een nieuwe uitdaging voor de theoretische informatica.