Voir la source de Algorithme de Shor

{{Sources à lier|date=février 2014}}

En [[arithmétique modulaire]] et en [[informatique quantique]], l’'''algorithme de Shor''' est un [[Algorithmique|algorithme]] [[calculateur quantique|quantique]] conçu par [[Peter Shor]] en 1994, qui [[Décomposition en produit de facteurs premiers|factorise]] un [[entier naturel]] ''N'' en temps [[notation O|O]]<math>((\log N)^3)</math> et en espace <math>O(\log N)</math>.

Beaucoup de [[Cryptographie asymétrique|cryptosystèmes à clé publique]], tels que le [[Rivest Shamir Adleman|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 [[nombre premier|nombres premiers]]. En l'état actuel des connaissances, il n'existe pas d'algorithme classique capable de faire cela en temps <math>O((\log N)^k)</math> 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'[[International Business Machines|IBM]], qui factorisa 15 en 3 et 5, en utilisant un calculateur quantique de 7 [[qubit]]s<ref>{{Lien web |langue=en |auteur1=Michael Ross |titre=IBM's Test-Tube Quantum Computer Makes History |url=https://web.archive.org/web/20121002124359/http://www-03.ibm.com/press/us/en/pressrelease/965.wss |site=Web Archive ibm.com |date=2001-12-19 |consulté le=2022-08-08}}.</ref>.

== Procédure ==
Soit ''N'' un [[entier naturel]] donné. L’algorithme de Shor vise à chercher un entier ''p'' compris entre 2 et <math>\sqrt N</math> qui divise ''N''.

Il consiste en deux éléments :
# Une réduction du problème de factorisation en un problème de [[Ordre (théorie des groupes)|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.

=== Partie classique ===
# Prendre un nombre pseudo-aléatoire ''a'' &lt; ''N''
# Calculer [[Plus grand commun diviseur|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 [[fonction périodique|période]] de la fonction <math>f:x \mapsto a^x\ \mbox{mod}\ N</math>, c’est-à-dire  le plus petit entier ''r'' pour lequel <math>f(x+r) = f(x)</math>.
# Si ''r'' est [[nombres pairs et impairs|impair]], retourner à l'étape 1.
# Si ''a'' <sup>''r''/2</sup> ≡ −1 (mod ''N''), retourner à l'étape 1.
# Les facteurs de ''N'' sont PGCD(a<sup>''r''/2</sup> ± 1, ''N''), ce qui résout le problème.

=== Partie quantique : sous-programme de recherche de période ===
# Commencer avec des registres d'entrée et de sortie de chacun log<sub>2</sub>''N'' qubits, et les initialiser à :
#::<math>N^{-1/2} \sum_x \left|x\right\rangle \left|0\right\rangle</math>
#: où ''x'' va de 0 à ''N –'' 1.
# Construire ''f''(''x'') comme une fonction quantique et l'appliquer à l'état précédent, pour obtenir
#:: <math>N^{-1/2} \sum_x \left|x\right\rangle \left|f(x)\right\rangle</math>
# Appliquer la [[Analyse harmonique sur un groupe abélien fini|transformée de Fourier]] quantique au registre d'entrée. La transformée de Fourier quantique sur ''N'' points est définie par :
#:: <math>U_{QFT} \left|x\right\rangle
= N^{-1/2} \sum_y e^{2\pi i x y/N} \left|y\right\rangle</math>
#: Ce qui donne l'état suivant :
#:: <math> N^{-1} \sum_x \sum_y e^{2\pi i x y/N} \left|y\right\rangle \left|f(x)\right\rangle</math>
# Effectuer une mesure. On obtient ainsi une certaine valeur ''y'' dans le registre d'entrée et <math>f(x_0)</math> dans le registre de sortie. Comme ''f'' est périodique, la probabilité de mesurer un certain ''y'' est donnée par
#:: <math>\left| N^{-1} \sum_{x:\, f(x)=f(x_0)} e^{2\pi i x y/N} \right|^2
= \left| N^{-1} \sum_{b} e^{2\pi i (x_0 + r b) y/N} \right|^2
</math>
#: Le calcul montre que cette probabilité est plus haute quand <math>y\times r /N</math> est proche d'un entier.
# Mettre ''y/N'' sous forme irréductible, et extraire le dénominateur ''r''′, qui est un candidat pour ''r''.
# Vérifier si ''f''(''x'') = ''f''(''x'' + ''r''′). Si c'est le cas, c'est terminé.
# Autrement, obtenir plus de candidats pour ''r'' en utilisant des valeurs proches de ''y'', ou multiples de ''r''′. Si un autre candidat marche, c'est terminé.
# Sinon, retourner à l'étape 1 du sous-programme.

=== Explication de l'algorithme ===
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 programmé 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.

==== Obtenir des facteurs à partir de la période ====

Les entiers inférieurs à ''N'' et [[premiers entre eux|premiers avec]] ''N'' forment un [[groupe (mathématiques)|groupe]] fini muni de la multiplication [[Congruence sur les entiers|modulo]] ''N'', qui est typiquement noté ('''Z'''/''N'''''Z''')<sup>×</sup>. La fin de l'étape 3 permet de déterminer un entier ''a'' dans ce groupe. Comme le groupe est fini, ''a'' possède (d'après le [[Théorème_d'Euler_(arithmétique)|théorème d'Euler]]) un ordre fini ''r'', défini comme plus petit entier positif tel que

:<math>a^r \equiv 1\ \mbox{mod}\ N</math>

Par conséquent, ''N'' | (''a'' <sup>''r''</sup> – 1). Supposons qu’il soit possible de déterminer ''r'', et que celui-ci est [[nombres pairs et impairs|pair]]. Alors
:<math>a^r - 1 = (a^{r/2} - 1) (a^{r/2} + 1) \equiv 0\ \mbox{mod}\ N</math>, d’où <math>N\ | (a^{r/2} - 1) (a^{r/2} + 1)</math>

''r'' est le ''plus petit'' entier positif tel que ''N'' divise (''a'' <sup>''r''</sup> – 1), donc ''N'' ne peut pas diviser (''a'' <sup>''r'' / 2</sup> – 1). Si ''N'' ne divise pas non plus (''a'' <sup>''r'' / 2</sup> + 1), alors ''N'' doit avoir un facteur commun non-trivial avec chacun des (''a'' <sup>''r'' / 2</sup> – 1) et (''a'' <sup>''r'' / 2</sup> + 1).

Preuve : notons (''a'' <sup>''r'' / 2</sup> – 1) et (''a'' <sup>''r'' / 2</sup> + 1) par ''u'' et ''v'' respectivement. ''N'' | ''uv'', donc ''kN'' = ''uv'' pour un certain entier ''k''. Supposons que PGCD(''u'', ''N'') = 1 ; alors ''mu'' + ''nN'' = 1 pour certains entiers ''m'' et ''n'' ([[Théorème de Bachet-Bézout|identité de Bézout]]). En multipliant de part et d’autre par ''v'', l’on trouve que ''mkN'' + ''nvN'' = ''v'', donc ''N'' | ''v''. Par contradiction, PGCD(''u'', ''N'') ≠ 1. Par un argument similaire, PGCD(''v'', ''N'') ≠ 1.

Ceci fournit une factorisation de ''N''. Si ''N'' est le produit de deux nombres premiers, elle est la ''seule'' factorisation possible.

==== Trouver la période ====

L'algorithme de recherche de période de Shor est fortement relié à la capacité d'un calculateur quantique à être dans de nombreux états simultanément. Les physiciens appellent ce comportement une « [[Principe de superposition quantique|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 [[Observable|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 accompli par la [[Analyse harmonique sur un groupe abélien fini|transformée de Fourier]] quantique.

Shor eut ainsi à résoudre trois problèmes : Tous ont été résolus « rapidement », c'est-à-dire avec un nombre de [[Calculateur quantique|portes quantiques]] [[P (complexité)|polynomial]] en <math>\log N</math>.

# Créer une superposition d'états. Ceci peut être fait en appliquant des [[Transformée de Hadamard#Applications|portes d'Hadamard]] à tous les qubits dans le registre d'entrée. Une autre approche serait d'utiliser la transformée de Fourier quantique (voir ci-dessous).
# Implémenter la fonction ''f'' comme une transformation quantique. Pour accomplir cela, Shor utilisa l'[[Exponentiation rapide|élévation au carré]] pour sa transformation d'exponentiation modulaire.
# Exécuter une [[transformation de Fourier]] quantique. En utilisant les portes NON contrôlées et les portes qubit à rotation unique, Shor conçut un circuit pour la transformée de Fourier quantique qui utilise juste <math>O((\log N)^2)</math> portes.

Après toutes ces transformations, une mesure fournit 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 <math>e^{2 \pi i b yr/N} = 1\,</math> 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é.

== Notes et références ==
{{Traduction/Référence|lang1=en|art1=Shor's algorithm|id1=7839275|type=note}}
{{Références}}

== Annexes ==
=== Bibliographie ===
* {{en}} Peter W. Shor, ''Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer''. {{arxiv|quant-ph/9508027}}
* {{en}} Michael A. Nielsen et Isaac L. Chuang, ''Quantum Computation and Quantum Information'', [[Cambridge University Press]], 2000{{Commentaire biblio|Un livre généraliste sur le calcul quantique}}
* {{Article| langue=en| titre=Peter Shor on the genesis of Shor’s algorithm| auteur1=David Zierler| auteur2=Ryan Dahn| périodique=[[Physics Today]]| date=7 mars 2025| doi=10.1063/pt.ifad.hcakdoi=| accès doi=libre| consulté le=10 mars 2025}}.

=== Articles connexes ===
* [[Information quantique]]
* [[Algorithme de Grover]]
* [[Algorithme de Deutsch-Jozsa]]

=== Liens externes ===
* [http://www.scottaaronson.com/blog/?p=208 Une explication] de l'algorithme de Shor, sans calculs, sur le [[blog]] de [[Scott Aaronson]]
* [https://python.jpvweb.com/python/mesrecettespython/doku.php?id=factorisation_shor Exemple] de programme calculant l'algorithme de Shor en [[Python (langage)|Python]] (avec des performances plus limitées que sur ordinateur quantique)

{{portail|arithmétique|informatique théorique}}

[[Catégorie:Théorie de l'information quantique]]
[[Catégorie:Informatique quantique]]
[[Catégorie:Algorithme de factorisation des entiers]]