Vous avez sous les yeux un nombre RSA gigantesque et une question revient immédiatement : un ordinateur quantique pourrait-il vraiment en retrouver les facteurs premiers ? La réponse courte est oui en théorie, car l’algorithme de Shor transforme la factorisation en recherche de période, mais cette conclusion dépend d’un circuit corrigé des erreurs et de ressources très supérieures à celles d’une démonstration sur un petit nombre. La différence entre une expérience pédagogique et une attaque cryptographique tient précisément là.

Le point à retenir avant d’écrire une seule porte quantique
- Idée centrale : la factorisation passe par la recherche de l’ordre d’un nombre modulo N.
- Partie quantique : l’estimation de phase et la transformée de Fourier quantique extraient une information périodique.
- Piège de programmation : un circuit qui factorise 15 en simulation ne représente pas une implémentation capable d’attaquer RSA.
- Conséquence pratique : RSA et les courbes elliptiques doivent déjà entrer dans une stratégie de migration post-quantique.
La période modulo N est le vrai cœur de l’algorithme
Shor ne cherche pas les diviseurs un par un. Il choisit un entier a premier avec N, puis cherche le plus petit entier positif r tel que ar ≡ 1 mod N. Cet entier s’appelle l’ordre de a modulo N. La démonstration publiée dans l’article original de Peter Shor repose sur cette réduction entre théorie des nombres et calcul quantique.
Une fois la période connue, la factorisation devient une opération classique. Si r est pair et si ar/2 ≠ -1 mod N, les valeurs suivantes peuvent révéler deux facteurs non triviaux :
p = gcd(ar/2 - 1, N)q = gcd(ar/2 + 1, N)
Le passage quantique sert donc à obtenir une période difficile à découvrir efficacement par les méthodes classiques. Les plus grands calculs de multiplication modulaire restent toutefois indispensables. C’est là que les explications trop rapides donnent une image trompeuse du procédé.
Avec 15, la mécanique devient visible en quatre étapes
Le nombre 15 est souvent utilisé parce qu’il permet de suivre chaque calcul à la main sans masquer la logique. Prenons a = 2. La suite des puissances modulo 15 boucle rapidement, et cette boucle contient déjà toute l’idée de Shor.
| Étape | Calcul | Résultat |
|---|---|---|
| Choix de la base | gcd(2, 15) |
1, la recherche peut continuer |
| Recherche de période | 21, 22, 23, 24 mod 15 |
2, 4, 8, 1, donc r = 4 |
| Valeur centrale | 2r/2 mod 15 |
22 mod 15 = 4 |
| Extraction des facteurs | gcd(4 - 1, 15) et gcd(4 + 1, 15) |
3 et 5 |
Le calcul échoue lorsque r est impair ou lorsque la valeur intermédiaire vaut -1 mod N. Dans ces deux cas, il ne faut pas modifier la formule au hasard : il faut choisir une nouvelle base a et relancer la recherche de période.
Pour un entier impair qui n’est pas une puissance d’un seul nombre premier, une exécution dispose d’une probabilité d’au moins 50 % de produire une séparation exploitable dans l’analyse pédagogique d’IBM Quantum. La borne cumulée atteint 87,5 % après trois essais et 96,875 % après cinq essais, à condition que les essais soient indépendants et que la partie quantique fournisse bien une information exploitable. Cette répétition n’est donc pas un défaut du programme : elle fait partie du caractère probabiliste de l’algorithme.
La partie quantique trouve r, mais le code autour décide du résultat
La machine quantique ne renvoie pas directement la valeur r. Elle applique une opération de multiplication modulaire, souvent notée Ua, puis utilise l’estimation de phase quantique. La transformée de Fourier quantique concentre la probabilité autour de fractions liées à la période, et une réduction par fractions continues permet ensuite de reconstruire un candidat pour r. Le cours IBM Quantum sur l’estimation de phase et la factorisation présente cette articulation entre sous-problème quantique et post-traitement classique.
Le pseudo-code suivant représente la partie de contrôle. Il ne remplace pas le circuit d’estimation de phase, mais il montre où se situent les décisions qui rendent une exécution valide ou inutile :
tant que vrai:
choisir a dans {2, ..., N - 2}
facteur = gcd(a, N)
si facteur > 1:
retourner facteur, N // facteur
r = recherche_quantique_de_l_ordre(a, N)
si r est invalide ou r est impair:
continuer
x = pow(a, r // 2, N)
si x == N - 1:
continuer
p = gcd(x - 1, N)
q = gcd(x + 1, N)
si p > 1 et q > 1:
retourner p, q
Le piège arrive au moment de programmer un premier exemple. La documentation de démonstration de Qiskit pour l’algorithme de Shor utilise notamment des constructions adaptées à de petits cas, avec des opérateurs unitaires et des circuits ciblés. C’est pratique pour comprendre les portes, mais une matrice explicitement construite devient vite trop coûteuse lorsque la taille de N augmente.
| Situation observée | Cause probable | Action à prendre |
|---|---|---|
| Un facteur apparaît dès le calcul du PGCD initial | La base choisie partage déjà un diviseur avec N | Conserver le facteur sans lancer de circuit quantique |
| La fraction mesurée ne donne pas un ordre vérifiable | Précision insuffisante, bruit ou nombre de mesures trop faible | Valider le candidat avec ar mod N avant toute factorisation |
| L’ordre obtenu est impair | La sortie est inutilisable pour la séparation par différence de carrés | Recommencer avec une autre base |
| Le service renvoie des comptages incomplets | Erreur d’exécution, de transport ou de récupération du résultat | Contrôler le statut, journaliser l’identifiant de tâche et appliquer une gestion des erreurs d’API avant de relancer |
Une vérification classique reste indispensable après chaque mesure. Sans elle, une fraction plausible peut être prise pour la bonne période alors qu’elle ne satisfait pas l’équation modulaire.
La menace concerne les courbes elliptiques, pas seulement RSA
Réduire Shor à « l’algorithme qui casse RSA » est trop étroit. Le même cadre quantique s’applique au problème du logarithme discret, qui soutient notamment les échanges de clés et les signatures fondés sur les courbes elliptiques. Le nom de la primitive change, mais le danger vient toujours d’un problème mathématique réputé difficile pour un ordinateur classique.
Une étude publiée en 2026 par une équipe de Google Research estime que le logarithme discret sur une courbe de 256 bits pourrait être traité avec moins de 1 200 qubits logiques et moins de 90 millions de portes de Toffoli, ou avec une autre architecture utilisant moins de 1 450 qubits logiques et moins de 70 millions de ces portes. Dans leurs hypothèses d’architecture supraconductrice, l’exécution nécessiterait moins d’un demi-million de qubits physiques. Ces chiffres concernent ECDLP-256, pas directement RSA-2048, et ils dépendent fortement de la correction d’erreurs et de l’organisation matérielle décrites dans l’étude de Google Research sur les ressources quantiques.
Lire aussi : API Mistral, de la première requête au déploiement fiable
Le mythe du test de tous les facteurs
Shor ne teste pas tous les diviseurs en parallèle comme une immense liste de candidats. Cette image donne une mauvaise intuition du circuit. Le calcul exploite les interférences quantiques pour faire ressortir une structure périodique, puis le traitement classique transforme cette structure en facteurs.
Cette distinction change la manière de coder. Une simulation qui parcourt directement les possibilités peut reproduire le résultat final, mais elle ne reproduit pas l’avantage quantique. Pour étudier l’algorithme, il faut donc séparer trois couches : l’arithmétique modulaire, le circuit de recherche de période et la reconstruction classique de l’ordre.
La cryptographie post-quantique change déjà les choix d’architecture
La menace reste liée à l’existence d’une machine quantique corrigée des erreurs suffisamment grande, mais attendre cette machine pour commencer l’inventaire cryptographique serait une mauvaise stratégie. Les données capturées aujourd’hui peuvent rester sensibles pendant des années, tandis que les protocoles utilisés dans une application sont souvent plus difficiles à remplacer que prévu.
Dans NIST IR 8547 sur la transition vers les standards post-quantiques, le NIST prévoit de déprécier après 2030 puis d’interdire après 2035, dans ses normes et recommandations, plusieurs mécanismes vulnérables comme RSA et l’échange de clés sur courbes elliptiques. Le même document recense notamment ML-KEM pour l’établissement de clés, ainsi que ML-DSA et SLH-DSA pour les signatures.
Pour une application existante, la première étape n’est pas de remplacer chaque appel cryptographique au hasard. Il faut établir une cartographie précise :
- repérer les certificats, bibliothèques et protocoles qui utilisent RSA, DH, ECDH ou ECDSA ;
- séparer l’établissement de clés des signatures numériques, car les remplaçants ne répondent pas au même usage ;
- isoler la cryptographie derrière une interface capable d’accueillir plusieurs implémentations ;
- prévoir des tests de taille, de latence et de compatibilité réseau pour les clés et signatures post-quantiques.
Le chiffrement symétrique et les fonctions de hachage ne sont pas la cible directe de la factorisation ou du logarithme discret. Le chantier prioritaire concerne donc la cryptographie asymétrique, souvent enfouie dans TLS, les certificats, la signature de logiciels ou les systèmes d’identité.
Le bon prototype dépend de votre objectif
Pour comprendre les mathématiques, je choisirais un petit entier composé dont la période peut être vérifiée à la main, puis je contrôlerais chaque candidat avec une puissance modulaire classique. Pour apprendre les circuits, je séparerais l’estimation de phase de l’arithmétique modulaire au lieu de commencer par une matrice unitaire géante. Pour un système en production, je laisserais l’algorithme de Shor dans le domaine pédagogique et je consacrerais l’effort à l’inventaire des primitives vulnérables et à la crypto-agilité.
La bonne question n’est donc pas seulement « Shor peut-il factoriser ce nombre ? ». Il faut aussi demander si la période a été reconstruite correctement, si le circuit est réellement généralisable et si l’architecture logicielle peut changer de primitive avant que la contrainte matérielle ne disparaisse.