La multiplication des nombres entiers est un problème qui occupe les mathématiciens depuis l'Antiquité. La méthode "babylonienne" que nous apprenons à l'école nous oblige à multiplier chaque chiffre du premier nombre par chaque chiffre du second. Mais quand les deux nombres ont chacun un milliard de chiffres, cela signifie un milliard de fois un milliard ou 10 ¹⁸ opérations.

Au rythme d'un milliard d'opérations par seconde, il faudrait un ordinateur un peu plus de 30 ans pour terminer le travail. En 1971, les mathématiciens Schönhage et Strassen ont découvert un moyen plus rapide, réduire le temps de calcul à environ 30 secondes sur un ordinateur portable moderne. Dans leur article, ils ont également prédit qu'un autre algorithme, qui n'a pas encore été trouvé, pourrait faire un travail encore plus rapide. Joris van der Hoeven, un chercheur CNRS du Laboratoire d'informatique de l'École Polytechnique LIX, et David Harvey de l'Université de Nouvelle-Galles du Sud (Australie) ont trouvé cet algorithme.

Ils présentent leurs travaux dans un nouvel article mis à la disposition de la communauté scientifique via l'archive en ligne HAL. Mais un problème soulevé par Schönhage et Strassen reste à résoudre :prouver qu'il n'existe pas de méthode plus rapide. Cela pose un nouveau défi pour l'informatique théorique.