Trente ans plus tard, l'affacturage quantique gagne en vitesse

L'algorithme de Shor permettra aux futurs ordinateurs quantiques de factoriser rapidement de grands nombres, compromettant ainsi de nombreux protocoles de sécurité en ligne. Un chercheur a désormais démontré comment y parvenir encore plus rapidement.

L'algorithme de Peter Shor est une méthode quantique permettant de factoriser rapidement de grands nombres. Cet algorithme, développé dans les années 1990 menace la cryptographie à clé publique utilisée pour la sécurité sur Internet.

La nouvelle avancée d'Oded Regev

Oded Regev, un informaticien de l'Université de New York, a développé une nouvelle variante de l'algorithme de Shor qui améliore la relation entre la taille du nombre à factoriser et le nombre d'opérations quantiques nécessaires. C'est la première fois qu'une telle amélioration est réalisée depuis la découverte de l'algorithme original.

Regev a combiné l'algorithme de Shor avec des techniques de cryptographie basée sur les réseaux (lattices), qui traitent de la géométrie de haute dimension.

Fonctionnement de l'algorithme de Regev

L'algorithme de Regev généralise la fonction périodique au cœur de l'algorithme de Shor en utilisant plusieurs dimensions. Au lieu de multiplier un seul grand nombre plusieurs fois, il multiplie des paires de petits nombres ensemble, puis multiplie les résultats entre eux. Cela réduit considérablement le nombre de multiplications de grands nombres nécessaires, ce qui accélère le calcul quantique.

Implications et défis

Bien que l'algorithme de Regev accélère la partie quantique du calcul, il nécessite plus de qubits (bits quantiques) que l'algorithme de Shor original. Les qubits sont fragiles et sujets aux erreurs, ce qui rend la gestion d'un grand nombre de qubits difficile.

Cependant, des travaux récents ont permis de réduire le nombre de qubits requis par l'algorithme de Regev, le rendant plus proche d'une implémentation pratique.

Il faut souligner que l'amélioration de l'algorithme de Shor par Regev montre qu'il est toujours possible de faire des découvertes surprenantes dans le domaine de l'informatique quantique, même sur des problèmes étudiés depuis des décennies. Il reste encore beaucoup d'algorithmes quantiques à découvrir.