En hurtigere metode til at gange meget store tal

Multiplikationen af ​​heltal er et problem, der har holdt matematikere beskæftiget siden antikken. Den "babylonske" metode, vi lærer i skolen, kræver, at vi multiplicerer hvert ciffer i det første tal med hvert ciffer i det andet. Men når begge tal har en milliard cifre hver, det betyder en milliard gange en milliard eller 10 ¹⁸ operationer.

Med en hastighed på en milliard operationer i sekundet, det ville tage en computer lidt over 30 år at gøre arbejdet færdigt. I 1971, matematikerne Schönhage og Strassen opdagede en hurtigere måde, reducere beregningstiden ned til omkring 30 sekunder på en moderne bærbar computer. I deres artikel, de forudsagde også, at en anden algoritme – endnu ikke fundet – kunne gøre et endnu hurtigere arbejde. Joris van der Hoeven, en CNRS-forsker fra École Polytechnique Computer Science Laboratory LIX, og David Harvey fra University of New South Wales (Australien) har fundet den algoritme.

De præsenterer deres arbejde i en ny artikel, der er tilgængelig for det videnskabelige samfund gennem det online HAL-arkiv. Men et problem, som Schönhage et Strassen rejste, mangler at blive løst:at bevise, at der ikke findes en hurtigere metode. Dette udgør en ny udfordring for teoretisk datalogi.