algorithme de Shor

Prenez 15 : ses facteurs 3 et 5 sont vite trouvés. Pour un entier formé de centaines de chiffres, cette décomposition peut devenir hors de portée des méthodes classiques connues. L'algorithme de Shor transforme le problème. Un calcul quantique cherche le rythme auquel des puissances reviennent au même reste dans une division. Une fois cette période obtenue, quelques calculs classiques peuvent révéler les facteurs.

L'algorithme de Shor est une méthode quantique de factorisation d'un entier composé. Pour l'entier à factoriser, noté N, il choisit un entier a sans facteur commun avec N. Il recherche ensuite l'ordre de a modulo N : le plus petit entier positif r tel que $a^r\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}N)a^r\; \backslash equiv\; 1\; \backslash pmod\; N$.

La partie quantique évalue simultanément de nombreux exposants, puis une transformée de Fourier quantique fait apparaître des informations sur cette période. Une mesure et un traitement classique permettent d'en déduire r avec une certaine probabilité. Si r est pair et si $a^{r\mathrm{/}2}\equiv ̸-1(\mathrm{m}\mathrm{o}\mathrm{d}N)a^\{r/2\}\; \backslash not\backslash equiv\; -1\; \backslash pmod\; N$, les plus grands diviseurs communs de a^r/2 − 1 et de a^r/2 + 1 avec N donnent des facteurs non triviaux. Sinon, on recommence avec une autre base ou une autre exécution.

Son temps de calcul théorique est polynomial en la taille binaire de N. Ce résultat concerne un ordinateur quantique capable d'exécuter un circuit assez grand et suffisamment fiable ; il ne décrit pas les capacités pratiques des machines actuelles. Une telle machine menacerait notamment le RSA, dont la sécurité repose sur la difficulté pratique de factoriser de grands produits de nombres premiers.

Pour factoriser un entier composé N, choisissez un entier a compris entre 2 et N − 1.
1. Calculez le plus grand diviseur commun de a et N ; s'il dépasse 1, un facteur est déjà trouvé.
2. Sinon, utilisez la procédure quantique pour rechercher l'ordre r de a modulo N.
3. Si r est pair et si a^r/2 n'est pas congru à −1 modulo N, calculez les deux plus grands diviseurs communs avec a^r/2 − 1 et a^r/2 + 1.
4. Gardez les facteurs non triviaux obtenus ; sinon, recommencez.

L'entrée utile est un entier composé N. La base a doit être choisie entre 2 et N − 1 ; si elle partage déjà un facteur avec N, le calcul classique du plus grand diviseur commun suffit. Dans le cas restant, la recherche quantique porte sur une fonction périodique de la forme $f(x)=a^{x}Nf(x)=a^x\; \backslash bmod\; N$.

La période mesurée doit conduire à une valeur paire de r et à deux facteurs non triviaux. Par exemple, une période impaire bloque l'étape fondée sur r/2 : il faut alors choisir une autre base ou répéter la procédure. Si N est premier, il n'existe aucune décomposition en facteurs non triviaux ; un test de primalité est l'outil adapté avant de lancer une factorisation.

On veut factoriser l'entier N = 15 et l'on choisit la base a = 2. Les données sont donc 15, 2 et le fait que leur plus grand diviseur commun vaut 1.

1. Les puissances de 2 donnent successivement les restes 1, 2, 4, 8, puis de nouveau 1 modulo 15. La suite forme ainsi un cycle de quatre valeurs, que la représentation associée rend visible. La période recherchée est donc r = 4.

2. La période 4 est paire. On calcule alors a^r/2 = 2² = 4, qui n'est pas congru à −1 modulo 15.

3. Les deux calculs classiques donnent :
$\gcd (4-1,15)=\gcd (3,15)=3\backslash gcd(4-1,15)=\backslash gcd(3,15)=3$
$\gcd (4+1,15)=\gcd (5,15)=5\backslash gcd(4+1,15)=\backslash gcd(5,15)=5$

Les facteurs trouvés sont 3 et 5. Le contrôle est direct : 3 × 5 = 15. Sur un ordinateur quantique, l'étape propre à Shor consiste à obtenir la période ; les calculs de plus grand diviseur commun restent classiques.

En cryptographie, Shor sert à évaluer ce qui arriverait aux clés RSA si un ordinateur quantique assez puissant et fiable devenait disponible. Tant que cette capacité n'existe pas, une attaque réelle emploie des méthodes classiques ; pour protéger durablement de nouvelles données, on privilégie des mécanismes postquantiques qui ne reposent pas sur la factorisation.

En recherche expérimentale, de petites instances servent à vérifier la préparation du circuit, la transformée de Fourier quantique et l'extraction de la période. Un résultat sur 15 valide une démonstration de principe ; il ne prouve pas que la machine peut traiter les tailles utilisées en cryptographie.

Pour apprendre l'algorithme, on sépare toujours la réduction classique de la factorisation et la recherche quantique de période. Cette séparation permet de contrôler chaque calcul à la main et de repérer si l'échec vient du choix de la base, de la mesure ou du post-traitement.

Algorithme de Shor et transformée de Fourier quantique. La transformée est une sous-routine qui fait ressortir la périodicité ; Shor est la procédure complète qui choisit une base, recherche une période puis extrait des facteurs. Exécuter seulement la transformée ne factorise donc pas 15.

Factorisation quantique et factorisation classique. Elles visent la même décomposition, mais le critère est la ressource employée : Shor exige un circuit quantique pour la recherche de période. Calculer directement que 15 = 3 × 5 par essais de divisions reste une méthode classique.

Menace théorique et cassage immédiat de RSA. L'existence de l'algorithme établit une vulnérabilité face à une machine quantique adéquate. Elle ne signifie pas qu'un ordinateur ordinaire, ni toute machine quantique actuelle, peut factoriser dès maintenant les grands modules RSA.

Une exécution peut échouer. La mesure quantique ne livre pas nécessairement une période exploitable, et la période obtenue peut être impaire. Le symptôme est l'impossibilité de former r/2 ou l'obtention de facteurs 1 et N. Il faut répéter la mesure ou changer de base.

Le cas charnière a^r/2 ≡ −1 modulo N. Dans ce cas, le calcul avec a^r/2 + 1 rend N lui-même au lieu d'un facteur utile. Une autre base doit être choisie. Dans l'exemple, 2² = 4 n'est pas congru à 14 modulo 15, donc ce blocage n'apparaît pas.

Polynomial ne veut pas dire immédiatement praticable. La complexité est mesurée en fonction du nombre de bits de N, mais l'exécution exige assez de qubits, de portes et de correction d'erreurs. Une factorisation de 15 ne permet donc aucune extrapolation directe vers une clé RSA.

La cible doit être composite. Pour un nombre premier, les seuls facteurs positifs sont 1 et le nombre lui-même. Le symptôme est l'absence de facteur non trivial, quel que soit le cycle observé. Il faut d'abord utiliser un test de primalité, puis réserver Shor aux entrées à factoriser.

Arithmétique modulaire — Pour maîtriser les restes, congruences et cycles sur lesquels repose la recherche de période.

Transformée de Fourier — Pour relier la détection de fréquences au rôle joué par sa version quantique dans Shor.

Factorisation — Pour replacer la décomposition d'un entier en facteurs dans son cadre arithmétique général.

Nombre premier — Pour distinguer les entrées déjà premières des entiers composés auxquels la factorisation s'applique.