Pour la première fois en 30 ans, des chercheurs du MIT viennent d’améliorer l’algorithme de Shor. Cela nous rapproche un peu plus du jour où les ordinateurs quantiques pourront casser les algorithmes de chiffrement actuels.
au sommaire
Des chercheurs du Computer Science & Artificial Intelligence Lab (CSAIL) du MIT (Massachusetts Institute of Technology)) viennent de mettre au point un nouvel algorithme quantique qui pourrait bientôt permettre de décrypter les systèmes cryptographiques complexes. En 1994, Peter Shor a créé un algorithme utilisant le calcul quantique pour factoriser un entier en nombres premiersnombres premiers. La création de cet algorithme est lourde de conséquences, car elle signifie que les communications et données protégées par les algorithmes de chiffrement les plus avancés pourraient être exposées grâce à un ordinateur quantiqueordinateur quantique.
Heureusement, il n'existe pas encore d’ordinateur quantique assez puissant, et les chercheurs travaillent sur des algorithmes de chiffrement résistants au calcul quantique. L'algorithme de Shor nécessite un ordinateur quantique avec 20 millions de qubitsqubits, alors que les plus puissants ont à peine dépassé le millier de qubits.
Cependant, il y a un an, Oded Regev a proposé un nouvel algorithme, basé sur celui de Shor, et qui nécessiterait beaucoup moins de portesportes quantiques, l'équivalent quantique de la porte logique et qui s'appuie sur des qubits. En contrepartie, il faudrait beaucoup plus de mémoire qui s'appuie également sur des qubits. Une nouvelle approche, donc, mais qui ne réduit pas la quantité de qubits nécessaire.
La première avancée en 30 ans
Le nouvel algorithme du MIT combine les avantages des deux : il est bien plus rapide, nécessite moins de mémoire, et de plus, est résistant au bruit quantique. Il s'appuie sur des chiffres de la suite de Fibonacci, ce qui permet de remplacer des opérations qui utilisent des carrés des chiffres par de simples multiplications. Cette méthode ne nécessite plus que deux unités de mémoire quantique pour calculer un exposant.
Ce nouvel algorithme ne fonctionnera pas sur les ordinateurs quantiques actuels, et n'améliore l'algorithme de Shor que pour les entiers de plus de 2 048 bits (des nombres à 617 chiffres). Il représente tout de même une avancée significative, la première dans ce domaine en 30 ans. De plus, les chercheurs pensent qu'il pourra aider à développer de nouveaux algorithmes de chiffrement plus résistants aux ordinateurs quantiques.
