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 et en espace . Beaucoup de cryptosystèmes à clé publique, tels que le RSA, deviendraient vulnérables si l'algorithme de Shor était un jour implanté 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 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. 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. Soit N un entier naturel donné. L’algorithme de Shor vise à chercher un entier p compris entre 2 et qui divise N. Il consiste en deux éléments : Une réduction du problème de factorisation en un problème de recherche d'ordre, qui peut être effectuée sur un ordinateur classique. Un algorithme quantique pour résoudre le problème de recherche d'ordre. Prendre un nombre pseudo-aléatoire a < N Calculer PGCD(a, N). Ceci peut être effectué par l'utilisation de l'algorithme d'Euclide. Si PGCD(a, N) ≠ 1, alors c'est un facteur non trivial de N, ce qui donne une solution au problème. Sinon, utiliser le sous-programme de recherche de période (ci-dessous) pour trouver r, la période de la fonction , c’est-à-dire le plus petit entier r pour lequel . Si r est impair, retourner à l'étape 1.