En arithmétique modulaire, l’algorithme de Shor est un algorithme quantique pour factoriser un nombre N en temps O((logN)3) et en espace O(logN), nommé en l'honneur de Peter Shor.
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((logN)k) pour n'importe quel k, donc, les algorithmes classiques connus deviennent 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 tous les 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.
Le problème que nous allons essayer de résoudre est le suivant, soit un entier donné N, nous essayons de trouver un autre entier p compris entre 1 et N qui divise N.
L'algorithme de Shor consiste en deux parties :
L'algorithme est composé de deux parties. La première partie transforme le problème de factorisation en un problème de recherche de période d'une fonction et peut être implémentée de façon classique. La seconde partie trouve la période en utilisant la transformée de Fourier quantique et est responsable de l'accélération quantique.
Les entiers inférieurs à N et premiers avec N forment un groupe fini muni de la multiplication modulo N, qui est typiquement noté (Z/NZ)×. Par la fin de l'étape 3, nous avons un entier a dans ce groupe. Comme le groupe est fini, a doit avoir un ordre fini r, le plus petit entier positif tel que
Par conséquent, N | (a r - 1). Supposons que nous sommes capable d'obtenir r et qu'il est pair. Alors
r est le plus petit entier positif tel que N divise (a r- 1), donc N ne peut pas diviser (a r / 2 - 1). Si N ne divise pas non plus (a r / 2 + 1), alors N doit avoir un facteur commun non-trivial avec chacun des (a r / 2 - 1) et (a r / 2 + 1).
Preuve : Pour simplifier, notons (a r / 2 - 1) et (a r / 2 + 1) par u et v respectivement. N | uv, donc kN = uv pour certain entier k. Supposons que PGCD(u, N) = 1; alors mu + nN = 1 pour certains entiers m et n (ceci est une propriété du PGCD.) En multipliant les deux côtés par v, nous trouvons que mkN + nvN = v, donc N | v. Par contradiction, PGCD(u, N) ≠ 1. Par un argument similaire, PGCD(v, N) ≠ 1.
Ceci nous fournit une factorisation de N. Si N est le produit de deux nombres premiers, ceci est la seule factorisation possible.
L'algorithme de recherche de période de Shor est fortement relié à la capacité d'un calculateur quantique d'être dans de nombreux états simultanément. Les physiciens appellent ce comportement une « superposition » d'états. Pour calculer la période d'une fonction f, nous évaluons la fonction en tous ses points simultanément.
Pourtant, la physique quantique ne nous permet pas d'accéder à toute l'information directement. Une mesure fournira seulement une parmi toutes les valeurs possibles en détruisant toutes les autres. Par conséquent nous avons à transformer avec précaution la superposition en un autre état qui retournera la réponse correcte avec une haute probabilité. Ceci est achevé par la transformée de Fourier quantique.
Shor eut ainsi à résoudre trois problèmes d'« implémentation ». Tous ont été implémentés « rapidement », ce qui veut dire qu'ils peuvent être implémentés avec un nombre de portes quantiques qui est polynomial en logN.
Après toutes ces transformations, une mesure fournira une approximation de la période r. Pour simplifier, assurons-nous qu'il existe un y tel que yr/N soit un entier. Alors la probabilité de mesurer y est 1. Pour voir cela, notons qu'alors
Pour tous les entiers b. Par conséquent, la somme qui nous donne la probabilité de mesurer y sera de N/r comme b prend globalement N/r valeurs et ainsi, la probabilité est 1/r. Il existe r y tels que yr/N soit un entier donc les probabilités totalisent 1.
Note : une autre manière d'expliquer l'algorithme de Shor est de noter que c'est juste l'algorithme d'estimation de phase quantique déguisé.