Multiplier de grands entiers : quasi linéaire, et après ?

Intervenant 10:00

À ton idée du défi que représente la multiplication de deux nombres composés, disons, d'un milliard de chiffres chacun ?

Intervenant 20:08

Ah ça c'est sûr que c'est gigantesque !

Intervenant 10:10

Oui, et pendant des décennies, même les supercalculateurs les plus puissants s'y cassaient les dents. Jusqu'à ce qu'en 2019, une nouvelle méthode vienne briser les limites de vitesse de l'arithmétique fondamentale. Bienvenue à l'écoute de cette émission, le podcast du magazine Tangente. Je suis ravie d'animer cette discussion aujourd'hui où l'on explore un acte si quotidien qu'on l'apprend à l'école primaire, la multiplication et surtout la révolution inattendue qu'elle vient de traverser.

Intervenant 20:38

Bonjour, et oui, c'est une opération vieille, de plusieurs millénaires, qu'on effectue machinalement. Mais l'algorithme même de la multiplication a été totalement bouleversé, fin mars 2019, par les mathématiciens David Harvey et Joris van der Hoeven.

Intervenant 10:52

Mais pour poser un peu le contexte, on peut légitimement se demander pourquoi chercher à améliorer la multiplication. Sur des petits nombres, le résultat est immédiat. Quel est l'intérêt concret de manipuler des nombres qui font un milliard de chiffres ?

Intervenant 21:05

Alors, ces calculs gigantesques, c'est en fait la base absolue de notre monde numérique. Ils sont au cœur de la cryptographie moderne, celle qui sécurise les transactions bancaires par exemple, ou encore dans la recherche de nouveaux nombres premiers.

Intervenant 11:19

D'accord, l'enjeu est donc vraiment colossal. Mais comment faisaient les ordinateurs avant cette découverte ? Si on reprend les bases de l'école, pour multiplier un nombre de trois chiffres par un autre de trois chiffres, on fait neuf petites multiplications.

Intervenant 21:33

C'est ça, on multiplie chaque chiffre par chaque chiffre.

Intervenant 11:36

Donc le temps de calcul augmente proportionnellement au carré de la taille d'une nombre initiale, c'est ce qu'on appelle un temps quadratique si je ne m'abuse.

Intervenant 21:44

C'est parfaitement ça. Ce qui est fascinant ici, c'est l'importance historique du problème. Cette méthode, elle date de l'Antiquité.

Intervenant 11:51

C'est comme si on venait soudainement de découvrir en 2019 une façon fondamentalement plus efficace de marcher. C'est fou quand on y pense.

Intervenant 21:58

Exactement. Pour utiliser une analogie, l'ancienne méthode de multiplication, c'est un peu comme si, dans un stade, chaque spectateur devait serrer la main de tous les autres, un par un.

Intervenant 12:08

Oula, ça en fait des poignées de main.

Intervenant 22:10

Voilà, si la taille de la foule double, le nombre de poignées de main quadruple. Avec des milliards de chiffres, cette méthode s'effondre sous son propre poids. Elle exige une puissance de calcul démesurée.

Intervenant 12:21

Alors comment contourner ce mur temporel ? Parce qu'en 2019, le fameux duo de chercheurs a prouvé que la multiplication de grands entiers pouvait se faire en un temps qu'ils appellent quasi linéaire. Ils ont même résolu une question ouverte depuis 1971. Concrètement, comment fonctionne ce raccourci ?

Intervenant 22:40

Le secret repose sur une approche bien connue en informatique, le diviser pour régner.

Intervenant 12:45

C'est-à-dire ?

Intervenant 22:46

On coupe les nombres.

Intervenant 12:47

Exactement. Au lieu de multiplier d'un seul bloc, l'algorithme découpe ces immenses nombres en petits morceaux. Ensuite, il utilise des outils mathématiques très puissants, qui sont liés au transformé de Fourier, pour remplacer la grande majorité de ces multiplications complexes par de simples additions. Ah, je vois. Donc, pour reprendre notre stade de tout à l'heure, c'est comme si on regroupait les spectateurs par sections. Au lieu que chacun se serre la main individuellement, on utilise une astuce mathématique pour comptabiliser les interactions entre les groupes entiers en un seul coup.

Intervenant 23:20

C'est une excellente comparaison. L'ordinateur effectue infiniment moins d'opérations redondantes. Et c'est ce qui permet d'arriver à leur nouvelle limite de vitesse.

Intervenant 13:28

Et quelle est cette limite exactement ?

Intervenant 23:31

Le nombre d'opérations devient proportionnel à la taille n du nombre multiplié par le logarithme népérien de n, ce qu'on note e n ln v n.

Intervenant 13:40

Bon, décortiquons tout ça. Je veux bien faire un peu l'avocat du diable.

Intervenant 23:44

Allez-y.

Intervenant 13:45

La formule ln de n, ça reste quand même très abstrait. Pourquoi voit-on apparaître un logarithme ici ? En général, c'est un concept que l'on croise avec des exposants, ça paraît très étrange de le retrouver au beau milieu d'une multiplication basique. Est-ce que ça veut dire que le temps de calcul

Intervenant 24:02

stagne ? Pas du tout. Ce fameux LN de N apparaît précisément à cause de ce découpage dont on parlait à l'instant. L'algorithme coupe continuellement les nombres massifs en deux, puis encore en deux, jusqu'à ce qu'ils soient assez petits pour être multipliés facilement.

Intervenant 14:17

D'accord.

Intervenant 24:18

Et cette structure en arbre qui se divise à chaque étape, elle produit par définition une progression logarithmique. L'élégance de ce gain d'efficacité est vraiment remarquable. Sans jargon inutile.

Intervenant 14:29

C'est là que ça devient vraiment intéressant. On comprend la mécanique, on a cassé une barrière théorique qui tenait depuis plus de 40 ans, mais est-ce vraiment la fin absolue de l'histoire mathématique de la multiplication ?

Intervenant 24:43

Eh bien non, et c'est la grande énigme actuelle. Il est peut-être possible de faire encore mieux.

Intervenant 14:48

Attendez, vraiment ?

Intervenant 24:50

Oui. En fait, il n'a jamais été formellement prouvé qu'un algorithme strictement linéaire, c'est-à-dire un temps proportionnel uniquement à n sans même le logarithme, était impossible. D'ailleurs, un futur article du magazine détaillera les rouages très pointus de l'algorithme de 2019.

Intervenant 15:08

C'est quand même étonnant de se dire qu'en mathématiques, on ne sache toujours pas prouver qu'une chose est impossible sur une opération aussi basique.

Intervenant 25:16

C'est vrai. Et cela soulève une question importante sur l'humilité scientifique. La frontière entre ce qu'on sait faire aujourd'hui et ce qu'il est théoriquement possible de faire est en perpétuel mouvement. La perfection absolue existe peut-être quelque part.

Intervenant 15:30

Pour résumer notre cheminement, on est donc partis d'une méthode antique, laborieuse, avec un temps de calcul quadratique. On a franchi un cap historique grâce au principe de « diviser pour régner » et à cette fameuse formule NLN de 2019.

Intervenant 25:43

Tout à fait.

Intervenant 15:44

Pour arriver aujourd'hui face au mystère non résolu du temps purement linéaire, ce qui laisse une dernière pensée provocatrice en suspens.

Intervenant 25:51

Laquelle ?

Intervenant 15:52

Eh bien, si une opération aussi élémentaire que la multiplication a pu cacher ses limites temporelles pendant des millénaires, Quelles autres évidences, que l'on manipule machinellement tous les jours, recèlent encore de profonds mystères théoriques, prêts à être bouleversés ? Voilà une belle réflexion pour clôturer cette émission. Merci pour l'écoute et à très bientôt pour de nouvelles découvertes passionnantes.