Dans l’épisode précédent, nous avons découvert que multiplier deux immenses nombres premiers était facile… mais que retrouver ces nombres à partir du résultat était extraordinairement difficile. Peter Shor n’a pas cherché à accélérer cette factorisation classique. Il a fait quelque chose de plus élégant : transformer la serrure en un problème de rythme.

Prenons un exemple minuscule : le nombre 15. Choisissons le nombre 2, élevons-le successivement à différentes puissances et ne conservons chaque fois que le reste après division par 15. Nous obtenons : 1 → 2 → 4 → 8 → 1 → 2 → 4 → 8… La suite revient à son point de départ tous les quatre pas.

Elle possède donc une période de 4. Et cette période contient une information surprenante. Sa moitié vaut 2. Calculons alors 2² : nous obtenons 4. Dans cet exemple, les deux nombres situés juste autour de 4 sont : 4 − 1 = 3 4 + 1 = 5 Et 3 × 5… donne précisément 15. Nous venons de retrouver ses facteurs sans les chercher directement.

Pour un grand nombre, les derniers calculs utilisent notamment le plus grand diviseur commun. Certaines tentatives échouent et l’algorithme recommence avec un autre nombre. Mais le principe demeure : découvrir la période permet aux mathématiques classiques de faire apparaître les facteurs.

Avec 15, nous pouvons trouver le rythme en écrivant la suite. Avec un nombre de 617 chiffres, cette période peut devenir gigantesque. La suivre pas à pas ferait perdre tout l’intérêt de l’opération. C’est ici que le processeur quantique intervient. Il prépare une superposition représentant de nombreuses positions possibles dans la suite et y encode leurs résultats.

Mais la mesurer immédiatement n’en révélerait qu’un seul. Shor utilise donc les interférences avant la mesure. Une opération appelée transformée de Fourier quantique agit un peu comme un analyseur musical. Lorsque plusieurs sons sont mélangés, l’analyse de leurs fréquences peut révéler la cadence qui se répète sans devoir isoler chaque vibration.

Dans le calcul quantique, les possibilités compatibles avec le rythme se renforcent. Celles qui ne correspondent pas à cette répétition tendent à s’annuler. La mesure ne livre toujours pas directement les facteurs. Elle produit des indices concentrés autour de certaines fréquences, à partir desquels un ordinateur classique reconstruit la période puis termine le travail.

Shor est donc un algorithme hybride : 🎲 le calcul classique choisit un point de départ ; ⚛️ le calcul quantique fait émerger le rythme ; 🧮 le calcul classique transforme ce rythme en facteurs et vérifie le résultat. Il ne teste pas magiquement tous les diviseurs en parallèle. Il réorganise le problème pour rendre mesurable une structure que nos méthodes classiques peinent à trouver.

C’est cette différence qui pourrait un jour faire céder RSA-2048. Mais « pourrait » reste le mot essentiel. L’algorithme existe depuis 1994, mais aucune machine quantique actuelle ne possède encore les qubits logiques, la correction d’erreurs et la profondeur de calcul nécessaires pour l’exécuter contre une véritable clé RSA-2048.

La serrure tient donc toujours. Pourtant, son plan d’ouverture théorique est public depuis plus de trente ans. Et RSA repose sur une idée publiée en 1978, avant le Web, les smartphones et le commerce en ligne. 🤔 Pourquoi notre monde connecté repose-t-il encore sur des serrures conçues au siècle dernier ?

C’est ce que nous découvrirons dans le prochain épisode. 🚁 Curiosity First. Learning together. 🔎 Sources : publication originale de Peter Shor · IBM Quantum · NIST