Multiplikationen av heltal är ett problem som har hållit matematiker sysselsatta sedan antiken. Den "babyloniska" metoden vi lär oss i skolan kräver att vi multiplicerar varje siffra i det första talet med varje siffra i det andra. Men när båda talen har en miljard siffror var, det betyder en miljard gånger en miljard eller 10 ¹⁸ operationer.

Med en hastighet av en miljard operationer per sekund, det skulle ta en dator lite över 30 år att slutföra jobbet. 1971, matematikerna Schönhage och Strassen upptäckte ett snabbare sätt, sänker beräkningstiden till cirka 30 sekunder på en modern bärbar dator. I deras artikel, de förutspådde också att en annan algoritm – som ännu inte har hittats – kunde göra ett ännu snabbare jobb. Joris van der Hoeven, en CNRS-forskare från École Polytechnique Computer Science Laboratory LIX, och David Harvey från University of New South Wales (Australien) har hittat den algoritmen.

De presenterar sitt arbete i en ny artikel som är tillgänglig för forskarvärlden via HAL-arkivet online. Men ett problem som tagits upp av Schönhage et Strassen återstår att lösa:att bevisa att det inte finns någon snabbare metod. Detta innebär en ny utmaning för teoretisk datavetenskap.