Algorithme de Shor

En arithmétique modulaire et en informatique quantique, l’algorithme de Shor est un algorithme quantique conçu par Peter Shor en 1994, qui factorise un entier naturel N en temps O ( ( log ⁡ N ) 3 ) {\displaystyle ((\log N)^{3})} et en espace O ( log ⁡ N ) {\displaystyle O(\log N)} . Beaucoup de cryptosystèmes à clé publique, tels que le RSA, deviendraient vulnérables si l'algorithme de Shor était un jour implémenté dans un calculateur quantique pratique. Un message chiffré avec RSA peut être déchiffré par factorisation de sa clé publique N, qui est le produit de deux nombres premiers. En l'état actuel des connaissances, il n'existe pas d'algorithme classique capable de faire cela en temps O ( ( log ⁡ N ) k ) {\displaystyle O((\log N)^{k})} pour n'importe quel k. Les algorithmes classiques connus deviennent donc rapidement impraticables quand N augmente, à la différence de l'algorithme de Shor qui peut casser le RSA en temps polynomial. Il a été aussi étendu pour attaquer beaucoup d'autres cryptosystèmes à clé publique. Cet algorithme a suscité le développement récent de la cryptographie post-quantique, non-vulnérable à l'algorithme de Shor ou ses variantes. Comme la plupart des algorithmes pour calculateur quantique, l'algorithme de Shor est probabiliste : il donne la réponse correcte avec une haute probabilité et la probabilité d'échec peut être diminuée en répétant l'algorithme. L'algorithme de Shor fut utilisé en 2001 par un groupe d'IBM, qui factorisa 15 en 3 et 5, en utilisant un calculateur quantique de 7 qubits. Vingt cinq ans plus tard le record du plus grand entier factorisé en pratique par l'algorithme de Shor n'a pas été grandement amélioré et stagne toujours de l'ordre de 32.