Pourquoi les ordinateurs quantiques n’ont-ils toujours pas réussi à factoriser 21 ?

• Explication de l’impression d’absence de progrès depuis la factorisation de 15 par un ordinateur quantique en 2001
• Un circuit pour factoriser 21 nécessite 100 fois plus de portes d’intrication que pour factoriser 15
• Cet écart s’explique par la complexité de la multiplication modulaire conditionnelle et par des optimisations particulières qui ne s’appliquent qu’à 15
• La correction d’erreurs quantiques et les limites matérielles relèvent encore davantage la barrière vers la factorisation de 21
• La plupart des factorisations de 21 rapportées jusqu’ici reposent surtout sur des astuces, sans effectuer de véritable multiplication au sens strict

---

Pourquoi les ordinateurs quantiques n’ont-ils toujours pas réussi à factoriser 21 ?

Pourquoi la factorisation de 21 n’est pas apparue après celle de 15

• En 2001, une expérience de factorisation de 15 avec un ordinateur quantique a eu lieu
• En 2025, il n’existe toujours pas de cas réussi de factorisation de 21
• Ce point alimente l’idée selon laquelle l’informatique quantique n’aurait connu aucun progrès
• Pourtant, lorsqu’on compare les circuits de factorisation de 15 et de 21, il existe une raison bien plus surprenante

Différences structurelles entre les circuits de factorisation de 15 et de 21

• Le circuit de factorisation de 15 se réalise avec seulement 21 portes quantiques (21 portes d’intrication)
  • 6 portes d’intrication qubit-à-qubit (portes CNOT et CPHASE) et
  • 2 portes Toffoli (chacune décomposée en 6 portes d’intrication), soit un total de 21 portes d’intrication
• Le circuit de factorisation de 21 requiert 191 CNOT, 369 Toffoli, soit 2405 portes d’intrication au total
  • Cela représente une charge de portes d’intrication 115 fois supérieure à celle de la factorisation de 15
  • La taille du circuit n’augmente pas simplement de 25 % ou d’un facteur 2, elle devient plus de 100 fois plus coûteuse
• Même en tenant compte du niveau d’optimisation des circuits, un écart allant jusqu’à 500 fois paraît réaliste

Pourquoi un tel écart apparaît-il ?

• Dans les circuits quantiques de factorisation (algorithme de Shor), le coût dominant provient de la multiplication modulaire conditionnelle
  • Pour un nombre N sur n bits, il faut effectuer à plusieurs reprises des multiplications modulaires conditionnelles sur un accumulateur
  • Dans le cas de 15, parmi 8 multiplications conditionnelles, 6 peuvent être traitées comme des multiplications par 1 (donc sans véritable opération)
    • La première multiplication peut être implémentée de façon quasi gratuite car l’entrée vaut 1
    • La deuxième (la seule autre restante) peut aussi être traitée à faible coût avec deux CSWAP
    • Au final, il ne faut réellement payer le coût que de 2 opérations
    • Cette structure est une propriété particulière de 15 : beaucoup de multiplications sont proches de 1, ce qui réduit fortement la charge
• En revanche, pour 21, les multiplications ne valent pas 1 et prennent diverses valeurs, donc chacune a un coût
  • Les 8 multiplications ont toutes un coût : l’augmentation n’est pas seulement de 4 à 5 fois, mais de 20 à 100 fois
  • Des multiplications par 4 ou 16, par exemple, ne peuvent pas être implémentées avec une structure de type CSWAP (swap conditionnel)
  • La complexité varie selon chaque multiplication et l’optimisation n’est pas simple

Limites concrètes du matériel et de la correction d’erreurs

• La factorisation de 15 réalisée autrefois (en 2001) l’a été sur un ordinateur quantique NMR, avec de fortes limites de passage à l’échelle
• Plus encore, la nécessité de la correction d’erreurs quantiques devient plus pressante
  • Si le nombre de portes augmente d’un facteur 100, le taux d’erreur doit être 100 fois plus faible
  • En pratique, il peut aussi être nécessaire d’augmenter le nombre de qubits d’un facteur 100, ce qui fait grimper le coût total jusqu’à 10 000 fois

Polémiques autour des tentatives de factorisation et résultats erronés

• Quelques articles récents affirment avoir réussi à factoriser 21 avec un ordinateur quantique, mais
  • dans les faits, ils omettent souvent l’étape de multiplication de l’algorithme ou simplifient le circuit en connaissant le résultat à l’avance
  • sans véritable opération de multiplication, on ne peut pas considérer cela comme une factorisation
  • ce sont des résultats superficiels qui ignorent la différence fondamentale entre une simple « recherche de période » et la factorisation elle-même
• Certains articles utilisent même des astuces de façon flagrante, au point que des papiers satiriques ont été publiés en réponse
  • il existe notamment divers papiers satiriques, comme des expériences reproduisant des records de champion de factorisation
  • on voit aussi continuer à apparaître des benchmarks comme le variational factoring, sans justification sérieuse quant au passage à l’échelle

Quel est alors le bon indicateur des progrès en informatique quantique ?

• À ce stade, la factorisation n’est pas le principal benchmark des progrès en informatique quantique
  • au-delà de 15, l’explosion des coûts rend la validation pratique difficile
• Des éléments comme l’introduction de la correction d’erreurs quantiques (par exemple l’amélioration des surface codes), ou
  • des changements d’architecture matérielle permettant de résoudre les problèmes de passage à l’échelle (par exemple le remplacement continu d’atomes neutres),
  • constituent plutôt des points d’observation bien plus importants pour mesurer des progrès réels

[GN⁺]

Avis Hacker News

• Cela vient du fait qu’on n’avait encore jamais factorisé en pratique un nombre plus petit. Si l’exécution du programme suppose que le compilateur connaît déjà la réponse, alors ce n’est pas une vraie factorisation, mais simplement « afficher 3 »

• Je me demande combien de quantum gates sont réellement nécessaires pour factoriser un nombre ayant un intérêt cryptographique. J’aimerais aussi savoir s’il existe une trajectoire concrète vers des ordinateurs quantiques utilisables au cours de ce siècle

  • On peut citer comme exemple l’estimation du tableau 5 de cet article, selon laquelle la factorisation d’un RSA 2048 nécessite environ 7 milliards de portes Toffoli (lien vers l’article). Le moyen d’atteindre des milliards d’opérations est justement la correction d’erreurs quantiques, et l’article indique qu’un surface code de distance 25 suffit. Dans ce cas, on passe de 1 400 qubits logiques à environ 1 million de qubits physiques bruités. La conférence de Samuel Jacques à PQCrypto vaut aussi le détour (YouTube). Je suis l’auteur de ce blog et de l’article associé
  • Cette question est difficile pour deux raisons. D’abord, on ne peut pas tracer une frontière claire de ce qui est « significatif sur le plan cryptographique ». Ensuite, l’architecture d’un QC réellement capable d’exécuter cette opération n’est pas encore clairement connue. C’est un peu comme estimer en 1985 le nombre de portes logiques classiques nécessaires pour construire un réseau de neurones. Cela dit, il semble certain qu’il en faudra plus de plusieurs millions. Troisièmement, il existe un compromis, dans la correction d’erreurs quantiques, entre un taux d’erreur plus faible des qubits physiques et le nombre de gates nécessaires pour construire des qubits virtuels corrigés de façon fiable. On ne sait pas encore jusqu’où les taux d’erreur des qubits physiques pourront baisser. Si l’informatique quantique connaît un développement comparable à celui de l’informatique classique au cours des 75 dernières années, alors la cryptographie actuelle serait probablement totalement neutralisée vers 2100. Les prédictions restent difficiles tant qu’il n’y a pas eu une innovation unique du type transistor. Le progrès technologique paraît toujours impossible, jusqu’à ce que quelqu’un trouve la première méthode. (Description de l’UNIVAC I)
  • Voir aussi ce tweet récent (lien vers le tweet). Du point de vue du grand public, cette trajectoire semble masquée par plusieurs énormes percées en science des matériaux
  • Pour RSA 4096, il faudrait grossièrement 10^7 qubits avec un taux d’erreur de 10^-4. Des calculs utiles en chimie quantique sont déjà possibles avec une centaine de qubits seulement, et comme les algorithmes post-quantum se diffusent progressivement, la motivation à développer des ordinateurs quantiques pour casser la cryptographie diminue. Je pense que l’informatique quantique progressera plus vite dans des directions sans rapport avec la cryptographie
  • Les chiffres les plus récents parlent d’environ 1 million de qubits à un taux d’erreur de 1e-4 (lien vers l’article). Le nombre de gates dépend, au niveau du code, de l’opération effectivement exécutée, et avec une « horloge » à 1 MHz (temps de cycle du code), le calcul complet prend environ une semaine. C’est une métrique plus difficile à atteindre que le nombre de qubits. Grâce à l’effet presque magique de la correction d’erreurs quantiques — le nombre de qubits requis diminue fortement quand le taux d’erreur baisse — un simple palier d’amélioration de la qualité des qubits peut faire chuter brutalement les besoins en qubits. En revanche, si l’on doit répartir les opérations sur plusieurs systèmes, la situation se dégrade fortement

• L’article « Replication of Quantum Factorisation Records with an 8-bit Home Computer, an Abacus, and a Dog » est intéressant (lire l’article)

• Je m’intéresse à la taille des circuits et à la faisabilité de la factorisation de nombres cryptographiquement significatifs comme RSA1024

  • Les estimations de coût pour RSA1024 ne sont pas obtenues par simple extrapolation de petits nombres (4 bits, etc.), mais à partir de conceptions de circuits adaptées à l’échelle réelle. Autrement dit, elles intègrent déjà implicitement le problème de discontinuité évoqué dans ce texte. Cette publication n’a donc pas d’impact sur les estimations de coût existantes
  • (À noter : l’optimisation du circuit de factorisation de 21 sera sans doute difficile à appliquer à la factorisation de grands nombres. Un coût 500 fois supérieur à celui du circuit de factorisation de 15 serait peut-être plus réaliste. Bien sûr, même un surcoût de 100× suffit à illustrer l’argument. Merci tout particulièrement à Noah Shutty d’avoir mené une recherche coûteuse sur ordinateur pour cette optimisation de circuit)
  • C’est un peu hors sujet, mais je me demande si les cryptographes sont désormais convaincus qu’il est pratiquement impossible de factoriser RSA1024, même avec d’énormes datacenters. À l’heure actuelle, même les algorithmes les plus rapides ne peuvent pas le factoriser dans des délais réalistes. Mais j’aimerais savoir s’il existe un consensus selon lequel aucune amélioration révolutionnaire de ces algorithmes n’est à attendre prochainement

• Je me demande si un jour un ordinateur quantique pourrait s’attaquer au RSA post-quantum (article lié). Certains estiment qu’il suffit d’utiliser des clés suffisamment grandes, car les opérations RSA classiques (génération de clé, chiffrement, déchiffrement) sont asymétriquement favorables face à l’algorithme de Shor. Cela produit un effet proche des puzzles de Merkle, avec la condition supplémentaire que l’attaquant doit nécessairement recourir à un ordinateur quantique. J’ai déjà généré une clé publique RSA de taille gigabit (fichier de clé). Le format est : 4 octets little-endian pour la taille de la clé en octets, puis la clé, puis son inverse (modulo 256^bytes). L’exposant public est 3

  • Le Post-Quantum RSA est une blague de djb, créée pour répondre à la question « ça ne serait pas sûr si on utilisait juste de grosses clés ? ». Il est conçu pour faire en sorte qu’un seul chiffrement prenne 100 heures avec une clé de 1 To. Même un ordinateur quantique ne peut pas le casser

• La faute de frappe « error corection » m’a bien fait rire

• J’ai du mal à comprendre le passage sur un « coût de circuit 500 fois supérieur à factorisation-15 ». L’auteur a déjà présenté un cas à 115×, donc je me demande comment des optimisations supplémentaires peuvent aboutir à un résultat pire

  • Cela signifie que l’énorme quantité de travail d’optimisation investie dans la conception de circuits de factorisation pour de petits nombres est irréaliste à reproduire pour de grands nombres. Autrement dit, il est intuitif qu’en général, quand le nombre à factoriser grandit, il faut environ 500 fois plus de gates, et non aussi peu que 115×
  • En pratique, à grande échelle, les gains d’optimisation diminuent, et l’on n’obtiendra probablement pas des bénéfices comparables à ceux du circuit pour N=21
  • Une implémentation minimale est instable et difficile à rendre fiable. Développer un circuit pratique nécessite beaucoup de recherche pour obtenir des qubits stables, et des notions comme le « temps de décohérence » sont également mentionnées. Le nombre de qubits ne peut donc qu’exploser
  • Le facteur 115× résulte d’un grand nombre d’optimisations (peu réalistes)

• Je me demande si l’idée principale de ce billet suggère que les besoins en circuits, en Big-O, pour la factorisation de Schorr sont superpolynomiaux

  • D’après le contenu du texte, le coût en gates provient principalement de O(n) opérations de multiplication modulaire, chacune pouvant être implémentée avec O(n^2) gates. Globalement, même dans le pire des cas, cela semble être une complexité à peu près cubique

• La raison de l’adoption des technologies cryptographiques PQ (post-quantiques) n’est pas forcément la certitude qu’un QC arrivera bientôt. On ne sait pas quand un QC apparaîtra, car cela dépend du rythme du progrès technique. Le but de la cryptographie est de trouver des méthodes qui soient, en théorie aussi, quasiment incassables. Si une attaque est théoriquement possible, alors elle peut aussi l’être physiquement, donc il faut s’y préparer. Pour ECC et RSA, une voie théorique d’attaque a déjà été identifiée ; même sans machine réelle, on considère donc qu’une attaque est possible. Il est donc tout à fait raisonnable de se préparer à l’avance, avant l’arrivée des QC. En revanche, pour SHA2, AES, ChaCha, etc., on ne voit pas de voie d’attaque réaliste, donc il n’y a pas de plan de remplacement immédiat. Le chiffrement n’est pas la seule application, ni forcément la plus importante, des QC. On espère encore des avancées inconnues dans des domaines variés comme les systèmes physiques, le repliement des protéines ou le machine learning

  • Je me demande s’il reste encore une marge de progression dans des domaines comme le repliement des protéines après AlphaFold. (article de référence)

  • Dans le cas des chiffrements à clé symétrique (AES, ChaCha, SHA-2), une attaque quantique revient essentiellement à diviser par deux la longueur de clé effective, comme dans les cas de 3DES et 2DES. En pratique, on ne peut pas affirmer qu’il s’agit exactement d’un simple facteur 2, car les performances d’un véritable ordinateur quantique ne sont pas équivalentes, mais il suffit de passer à AES-256 et le problème disparaît. Là où il faut se concentrer, c’est sur le Key Exchange. La raison est que le Key Exchange sert à convenir d’une clé secrète sans que les deux parties aient à la révéler directement. Si un Quantum Computer existe, il peut alors relire des conversations passées qui ont été enregistrées. Percer un algorithme de signature ne permet pas de remonter le temps pour signer rétroactivement, mais casser le Key Exchange expose toutes les conversations passées d’un coup. C’est donc le remplacement sûr du Key Exchange qui est urgent