Une avancée majeure après 30 ans : L’amélioration de l’algorithme de Shor par le MIT

La première avancée en 30 ans

Des chercheurs du Computer Science & Artificial Intelligence Lab (CSAIL) du MIT viennent de réaliser une percée importante en améliorant l’algorithme de Shor, une première depuis sa création en 1994. Cet algorithme est essentiel car il exploite les capacités du calcul quantique pour factoriser des entiers en nombres premiers, une technique fondamentale pour casser les systèmes de chiffrement actuels, comme le RSA, qui repose sur la difficulté de factoriser de grands nombres.

Progrès vers le décryptage quantique

L’algorithme de Shor pourrait en théorie permettre aux ordinateurs quantiques de déchiffrer des données sécurisées, ce qui a soulevé des inquiétudes quant à la sécurité des systèmes de chiffrement modernes. Toutefois, à ce jour, aucun ordinateur quantique n’est suffisamment puissant pour mettre en œuvre cet algorithme à grande échelle, car il nécessiterait environ 20 millions de qubits alors que les machines actuelles en comptent tout juste quelques milliers.

Une nouvelle approche proposée

Il y a un an, Oded Regev a proposé un nouvel algorithme dérivé de celui de Shor, visant à réduire la complexité des opérations en nécessitant moins de portes quantiques. Cependant, cela augmenterait considérablement les besoins en mémoire, elle-même basée sur des qubits.

Le nouvel algorithme du MIT

Les chercheurs du MIT ont franchi une étape supplémentaire en combinant les avantages des approches existantes. Leur nouvel algorithme est plus rapide, nécessite moins de mémoire, et est résistant au bruit quantique, un facteur crucial pour la stabilité des calculs dans les systèmes quantiques. Ils ont utilisé des chiffres de la suite de Fibonacci pour simplifier les calculs, remplaçant certaines opérations complexes par de simples multiplications. Cette avancée permet de réduire les besoins en mémoire quantique à seulement deux unités, bien que l’algorithme ne soit applicable qu’à des entiers de plus de 2 048 bits.

Conclusion

Même si ce nouvel algorithme ne peut pas encore être utilisé sur les ordinateurs quantiques actuels, il représente un progrès significatif, la première avancée majeure en 30 ans dans ce domaine. Il ouvre également la voie à de nouvelles méthodes pour créer des systèmes de chiffrement plus résistants face à l’essor des ordinateurs quantiques.