118 Partages

L’un des domaines de recherche des mathématiques est le perfectionnement et l’amélioration des algorithmes et méthodes de calcul dans le but d’améliorer l’efficacité et la rapidité des systèmes qui ont quotidiennement affaire à de très grands nombres. Récemment, deux mathématiciens ont mis au point un nouvel algorithme permettant d’augmenter considérablement la rapidité de calcul dans la multiplication de grands nombres. Une avancée qui pourrait bénéficier aux ordinateurs actuels et futurs.

Deux mathématiciens australiens et français ont mis au point un nouveau moyen de multiplier les nombres, tout en résolvant un casse-tête algorithmique qui a rendu perplexes les plus grands esprits mathématiques depuis près d’un demi-siècle. Pour la plupart d’entre nous, nous multiplions des nombres relativement petits en nous rappelant nos tables de multiplication — une aide incroyablement pratique, inventée pour la première fois par les Babyloniens il y a environ 4000 ans.

Mais que faire si les nombres deviennent plus grands ? Si les nombres deviennent difficiles à manier — et en supposant que nous n’ayons ni calculatrice ni ordinateur — la plupart d’entre nous se tourneraient alors vers la multiplication longue : autre astuce utile que nous apprenons à l’école, et une technique fiable pour multiplier fondamentalement plusieurs nombres.

Il n’y a qu’un seul problème avec la multiplication longue : la méthode est lente. La raison de cette lenteur est que, pour chaque chiffre de chaque nombre du problème, vous devez effectuer une opération de multiplication distincte, avant d’ajouter tous les produits.

Bien que cela ne soit pas un problème limitant du quotidien pour la plupart des gens, c’est un problème pour les ordinateurs, car leurs propres limites dans l’exécution des calculs sont imposées par les limites des mathématiques abstraites que nous pouvons comprendre nous-mêmes.

Fondamentalement, la multiplication longue est un algorithme, mais ce n’est tout simplement pas un outil particulièrement efficace, car le processus est inévitablement fastidieux. Comme l’explique le mathématicien David Harvey de l’UNSW en Australie dans la vidéo ci-dessous, dans une multiplication où les deux nombres ont 3 chiffres (n = 3), le nombre d’opérations de multiplication distinctes impliquées est en réalité de 9, ce qui correspond à n² :

Le problème, c’est que plus les nombres sont grands, plus la quantité de travail à accomplir augmente également, et est toujours représentée par n élevé au carré. Bien qu’il soit inefficace, l’algorithme de multiplication long était en fait l’algorithme de multiplication le plus avancé des années 1960, lorsque le mathématicien russe Anatoly Karatsuba a découvert que n1.58 était possible.

Cliquez ici pour supprimer les publicités.

Une décennie plus tard, deux mathématiciens allemands ont réalisé une autre percée : l’algorithme de Schönhage-Strassen, qui supposait que d’autres améliorations de l’algorithme initial étaient possibles.

« Ils ont prédit l’existence d’un algorithme qui multiplie les nombres à n chiffres en utilisant essentiellement n * log (n) opérations de base » explique Harvey. « Notre article donne le premier exemple connu d’algorithme permettant d’atteindre cet objectif ».

Sur le même sujet : Pour la toute première fois, une femme remporte le prestigieux prix Abel de mathématiques

Selon les chercheurs, multiplier deux nombres ensemble d’un milliard de chiffres chacun par un processus de multiplication longue prendrait plusieurs mois à calculer. En utilisant l’algorithme de Schönhage-Strassen, cela prendrait moins de 30 secondes. Et avec leur nouveau concept, l’opération serait encore plus rapide et pourrait même représenter l’algorithme de multiplication mathématiquement le plus performant. L’algorithme a été publié sur le serveur ouvert HAL.

« En ce sens, notre travail devrait être la solution finale et définitive du problème, bien que nous ne sachions pas encore comment le prouver de manière rigoureuse » déclare Harvey. « Les gens sont à la recherche d’un tel algorithme depuis près de 50 ans. Ce n’était pas évident de prévoir que quelqu’un réussirait finalement ».

Il est à noter que le nouvel algorithme ne serait utile que pour multiplier de très grands nombres. Quelle taille exactement ? « Nous n’en avons aucune idée » expliquent les chercheurs, bien qu’un exemple cité dans l’article corresponde à 10’214’857’091’104’455’251’940’635’045’059’417’341’952.

« J’étais très étonné que cela ait été fait » confie le chercheur en informatique Martin Fürer, de la Penn State University. Fürer lui-même a essayé de réorganiser l’algorithme de Schönhage-Strassen il y a plus de dix ans, mais a finalement interrompu son travail. « Cela me semblait tout à fait désespéré ».

Source : HAL

Une réponse

  1. Manu D.

    C’est une excellente nouvelle, quand on sait que la multiplication est largement utilisée en informatique (sécurité, simulations, jeux vidéos, …)
    Malheureusement, je crains qu’il sera plus facile pour les pirates de casser des systèmes de sécurités, puisque ceux-ci se basent sur le fait qu’il est compliqué de trouver la décomposition en facteurs premiers de très (très) grand nombres. Et si la multiplication de grand nombres est considérablement accélérée, les attaques par brute force seront plus efficaces.
    Affaire à suivre donc.

    Répondre

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée.

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur comment les données de vos commentaires sont utilisées.

118 Partages
118 Partages
Partager via
Copier le lien