La multiplicación de números enteros es un problema que ha mantenido ocupados a los matemáticos desde la Antigüedad. El método "babilónico" que aprendemos en la escuela requiere que multipliquemos cada dígito del primer número por cada dígito del segundo. Pero cuando ambos números tienen mil millones de dígitos cada uno, eso significa mil millones de veces mil millones o 10 ¹⁸ operaciones.

A una velocidad de mil millones de operaciones por segundo, una computadora tardaría un poco más de 30 años en terminar el trabajo. En 1971, los matemáticos Schönhage y Strassen descubrieron una forma más rápida, reduciendo el tiempo de cálculo a unos 30 segundos en una computadora portátil moderna. En su artículo, también predijeron que otro algoritmo, aún por encontrar, podría hacer un trabajo aún más rápido. Joris van der Hoeven, un investigador del CNRS de la École Polytechnique Computer Science Laboratory LIX, y David Harvey de la Universidad de Nueva Gales del Sur (Australia) han descubierto ese algoritmo.

Presentan su trabajo en un nuevo artículo que está disponible para la comunidad científica a través del archivo HAL en línea. Pero queda por resolver un problema planteado por Schönhage et Strassen:demostrar que no existe un método más rápido. Esto plantea un nuevo desafío para la informática teórica.