9 octobre 2026Français
P vs NP : le guide du chat ninja pour gagner un million de dollars
Le 7 octobre 2026, Vitalik Buterin a publié sur X un fil qu’on a lu comme un avertissement sur l’informatique quantique, alors qu’il parlait d’autre chose. Le sujet était la proposition de Justin Drake de passer en « mode bunker » et de migrer les fonds vers de nouvelles adresses, face au risque que les mathématiques accélérées par l’IA commencent à casser la cryptographie sur réseaux euclidiens. Et au milieu de l’argument, presque en passant, arrive la phrase qui soutient tout le reste :
Théoriquement, bien sûr, il est possible que les hachages soient cassés eux aussi (par exemple, P = NP impliquerait cela). Mais je pense que P = NP est très improbable. Et intuitivement, il est bien plus probable qu’un objet mathématique n’ait aucune structure exploitable (comme les hachages le prétendent), qu’un objet mathématique qui aurait exactement trois formes de structure exploitable et pas une quatrième secrète que nous n’avons pas encore découverte.
Buterin ne discutait pas le problème du millénaire. Il s’en servait comme plancher. Et c’est là l’étrangeté que cet article veut regarder en face : le monde numérique entier tient sur une conjecture que personne ne sait démontrer, en pariant qu’elle est vraie. Chaque signature, chaque hachage, chaque coffre, chaque message chiffré que tu envoies dans une journée est un pari sur P ≠ NP.
Six étapes et neuf planches, avec un million de dollars qui attend dans un coffre. Le parcours peut se faire en entier en croyant que l’histoire se termine à « personne ne sait, et si P = NP tout s’écroule ». Elle ne se termine pas là : la conjecture qui soutient le monde numérique n’est pas celle dont la cryptographie a besoin, et c’est de cela qu’il s’agit ensuite.
Étape 1 : P — ce qu’on résout vite

P est la classe des problèmes qu’un ordinateur résout en temps polynomial : le travail croît de façon raisonnable quand l’entrée croît. Trier une liste, multiplier deux nombres, trouver le chemin le plus court sur une carte. Dire « rapide » ici est une promesse mathématique sur la croissance, pas sur les secondes : un algorithme peut être polynomial et pourtant mille fois pire qu’un autre algorithme polynomial.
Et il faut le dire d’emblée, parce que c’est la moitié du malentendu : P n’est pas « ce que les ordinateurs savent faire ». C’est ce qu’ils savent faire dans le pire cas imaginable pour chaque taille. En pratique, des problèmes NP-difficiles sont résolus tous les jours : les solveurs SAT expédient des instances industrielles à millions de variables, en vérification matérielle et en planification. La théorie parle du pire cas ; l’ingénierie vit du cas moyen.
Étape 2 : NP — ce qu’on vérifie vite

NP est la classe des problèmes dont la solution, une fois que quelqu’un te la donne, se vérifie vite. Le Sudoku : le remplir de zéro peut prendre une éternité ; regarder une grille complète et dire « oui, c’est valide » te prend une minute. Le problème du voyageur de commerce : trouver la route la plus courte entre cinquante villes est un enfer ; vérifier qu’un itinéraire proposé mesure bien ce qu’il annonce, non.
Et voici l’exemple qui nous importe : factoriser un nombre énorme. Multiplier deux nombres premiers de mille bits est instantané. Retrouver ces nombres premiers à partir du produit est — pour autant qu’on sache — impossible en pratique. RSA, ECDSA, Diffie-Hellman, la signature avec laquelle tu transfères de l’argent : tout cela vit de cette asymétrie.
Avec une précision qui sera ensuite la clé de cet article : la factorisation est dans NP et aussi dans co-NP, et on ne sait pas si elle est NP-complète. On croit que non. Retiens ce fait, parce que c’est lui qui casse le récit optimiste du « si P ≠ NP, ma cryptographie est à l’abri ».
La matrice de diagnostic

| Dimension | P | NP |
|---|---|---|
| Résoudre (créer la réponse) | Facile et efficace | Terriblement difficile |
| Vérifier (contrôler la réponse) | Facile et efficace | Facile et efficace |
| Le monde réel | Multiplier 15 × 15 | Casser la sécurité d’une banque |
Le tableau cache un piège : P est contenu dans NP. Tout ce que tu peux résoudre vite, tu peux évidemment le vérifier vite. La question à un million n’est pas de savoir si P et NP diffèrent en général — personne n’en doute — mais s’ils diffèrent complètement, ou si cette différence est une illusion qui s’évapore quand on trouve la bonne astuce.
Un chiffre pour mesurer le cadenas : le record mondial de factorisation (RSA-250, février 2020) a atteint 829 bits et a coûté environ 2 700 années-CPU réparties sur des dizaines de milliers de machines. RSA-2048 est toujours intact. La marge n’est pas du double : elle est astronomique, et c’est pour cela que nous vivons tranquilles.
Étape 3 : la grande question

La question tient en une phrase, et elle est si simple qu’elle ressemble à un piège :
Tout problème dont la solution se vérifie vite peut-il aussi se résoudre vite ?
P = NP signifie que vérifier et résoudre sont, au fond, le même travail. P ≠ NP signifie qu’il existe des problèmes réellement difficiles : qu’il y a une flèche qu’on ne peut pas retourner.
Steve Cook l’a formulée en 1971 et Leonid Levin en 1973, mais l’intuition est plus ancienne : en 1956, Kurt Gödel écrivait à John von Neumann pour se demander combien d’étapes coûterait le fait de trouver une démonstration, comparé au fait de la contrôler. Personne n’a répondu à cette lettre. En 2000, le Clay Mathematics Institute l’a inscrite sur sa liste des sept problèmes du millénaire, avec un million de dollars pour chacun. Un seul a été résolu : Poincaré, en 2003. Grigori Perelman a refusé le prix.
Étape 4 : imagine le chaos

Si P = NP était vrai, deux mondes s’ouvrent en même temps.
La branche utopique est celle qu’on raconte sur scène : optimisation parfaite, conception instantanée de médicaments, repliement des protéines, logistique, IA sans plafond, démonstrations mathématiques trouvées par machine. Tout ce que nous résolvons aujourd’hui par force brute ou par approximation deviendrait exact.
La branche apocalyptique est celle qui nous importe : RSA et les courbes elliptiques tombent, les hachages tombent, la signature de tout ce que tu as signé un jour tombe. Il n’y aurait pas de « vie privée plus faible » : il n’y aurait pas de vie privée. Tout message chiffré stocké aujourd’hui est un message en clair du futur, parce que l’attaquant n’a qu’à attendre que l’algorithme arrive.
Trois nuances qui restent souvent de côté et qu’il faut dire :
- L’effondrement n’a pas besoin d’être instantané. Un algorithme polynomial peut être un polynôme à exposant absurde : si le meilleur algorithme pour SAT tourne en n^1000, ta cryptographie tient toujours en pratique. P vs NP interroge la forme de la courbe, pas l’horloge.
- La démonstration pourrait ne pas donner d’algorithme. Si quelqu’un prouve P = NP de façon non constructive — par contradiction, ou avec un argument qui ne produit pas la machine —, il gagne le million et ne casse rien. C’est un cas rare mais parfaitement concevable.
- Les ordinateurs quantiques ne sont pas un raccourci vers P = NP. Shor (1994) casse RSA et les courbes elliptiques, oui, mais parce que la factorisation a une structure algébrique exploitable — pas parce que le quantique résout les problèmes NP-complets. Aucun problème NP-complet n’est connu comme résoluble en temps polynomial quantique, et on croit qu’aucun ne l’est. Grover ne donne qu’une racine carrée d’avantage. L’informatique quantique ne menace pas l’échafaudage de P ≠ NP ; elle le menace par un autre côté.
Le cas Vitalik : hachages, réseaux euclidiens et le bruit qui compte vraiment

Revenons au fil du 7 octobre, parce qu’il contient une leçon de méthode. Buterin ne désignait pas P = NP comme le danger. Au contraire : il disait que, pour les hachages, P = NP est le seul danger réel, et que pour cette raison même les hachages sont la partie la plus solide de l’écosystème. Un hachage est conçu pour n’avoir aucune structure exploitable. Et il est bien plus plausible qu’un objet mathématique n’ait aucune structure, qu’un objet mathématique qui aurait trois formes de structure et dont aucune ne cache une quatrième.
Le danger qu’il voit est ailleurs : les réseaux euclidiens (ML-DSA, FHE, la cryptographie post-quantique que tout le monde adopte précisément parce que les courbes elliptiques vont tomber). L’argument, dans ses mots, est celui des « squelettes dans le placard » : la factorisation était crue difficile jusqu’à ce que des décennies de mathématiciens intelligents la dégradent de 2^(n/2) à 2^O(n^(1/3)) et obligent les clés RSA à mesurer 400 octets au lieu de 64. Et s’il existait des améliorations de ce calibre, cachées pour les réseaux euclidiens, que nous ne sommes pas assez intelligents pour trouver mais qu’un bot trouvera bientôt ? Sa recommandation pratique : pour tout ce qui est à base de réseaux euclidiens, multiplie les tailles de clé par dix ; et partout où c’est possible, reste sur les hachages.
Cela ne contredit pas le reste de l’article : cela le complète. Aujourd’hui, la menace concrète contre la cryptographie n’est pas P = NP. C’est du cryptanalyse réel, assisté par IA, contre des hypothèses de dureté concrètes. Et pourtant l’endroit où la conversation finit toujours est le même : (par exemple, P = NP impliquerait cela). C’est le plancher de l’immeuble, et nous savons tous qu’il est là.
La partie qui casse le récit : P ≠ NP ne suffit pas
Voici le point qui, dans un texte sur la souveraineté, ne peut pas être sauté.
P ≠ NP ne te donne pas la cryptographie. Tout ce que nous utilisons — des hachages qu’on ne peut pas inverser, des signatures que personne ne peut falsifier — repose sur quelque chose de plus tranchant : des fonctions à sens unique, c’est-à-dire des problèmes difficiles en moyenne, pas seulement dans le pire cas. Et la difficulté en moyenne est un monde complètement différent de celui dont parle P vs NP.
Russell Impagliazzo l’a raconté en 1995 avec un exercice qui mériterait sa place dans tout programme : les cinq mondes possibles.
- Algorithmica : P = NP. La cryptographie est impossible.
- Heuristica : P ≠ NP, mais les problèmes difficiles sont faciles en moyenne. La cryptographie est impossible là aussi.
- Pessiland : des problèmes difficiles en moyenne existent, mais les fonctions à sens unique n’existent pas. P ≠ NP est vrai et pourtant il n’y a aucune cryptographie. Pas de générateurs pseudo-aléatoires non plus : le monde est froid, déterministe et lisible par n’importe qui.
- Minicrypt : les fonctions à sens unique existent. Il y a des hachages, du chiffrement symétrique, des MAC. Il n’y a pas de cryptographie à clé publique : pas de signatures, pas d’échange de clés, pas de blockchains.
- Cryptomania : les fonctions à sens unique à trappe existent. Il y a de la clé publique, des signatures, de la monnaie numérique. C’est le monde où nous vivons — ou celui que nous supposons habiter.
La leçon est que la cryptographie ne vit pas de P ≠ NP. Elle vit d’un pari plus fin : que la dureté du pire cas peut être fabriquée et transportée jusqu’à ta clé, en moyenne, avec une distribution que tu contrôles. Et ce pari est plus fort que l’autre : s’il existe des fonctions à sens unique, alors P ≠ NP (parce qu’inverser, c’est vérifier, et trouver la préimage, c’est résoudre). La réciproque n’est pas connue. Autrement dit : prouver P ≠ NP serait une grande avancée en mathématiques et pas une assurance pour ta vie privée.
Et il y a un détail de plus. Souviens-toi de la factorisation : elle est dans NP et dans co-NP, et on ne croit pas qu’elle soit NP-complète. Ce qui veut dire que la dureté de RSA ne se déduit pas de P ≠ NP, même si demain quelqu’un démontre P ≠ NP de la façon la plus rigoureuse possible. Nous vivons dans une maison à deux fondations : une visible et vénérée (P ≠ NP) et une réelle et bien plus fragile (la dureté en moyenne). Quand on parle de « sécurité démontrée », on parle presque toujours de la première.
La clé est aussi la porte
Le « mode bunker » se résume en une phrase : déplace tes fonds vers des adresses fraîches, qui n’ont jamais rien signé, pour que ta clé publique reste cachée derrière le hachage de l’adresse. La cryptographie est correcte : si la clé publique n’a jamais été révélée, il n’y a nulle part où prendre la privée — ni avec le quantique, ni sans lui. Le conseil est solide pour un trésor.
Le problème, c’est que dans ce que nous construisons, la clé ne garde pas un trésor : c’est un nom.
Chez RHM Seguros, l’e-mail d’entreprise n’a pas de mot de passe : tu entres en connectant le portefeuille et en signant un message avec un nonce. Dans Ius et ChatWallet, l’identité est la paire de clés : la norme du lien Ğ1 que nous avons écrite, ce sont deux signatures croisées qui déclarent qu’une adresse 0x… et un compte g1… sont la même personne, et ce lien reste sur la chaîne. Nous signons pour entrer, pour nous identifier, pour certifier que quelqu’un est quelqu’un, pour qu’un autre puisse lire ce que nous publions. Si l’adresse qui t’identifie doit rester vierge pour toujours, tu ne peux plus signer — c’est-à-dire que tu ne peux plus être.
Et déménager n’est pas gratuit. Dans Ğ1 v1, une clé était une identité : la changer, c’était révoquer l’identité et rassembler cinq nouvelles certifications, avec deux mois de fenêtre et la patience de cinq personnes. Dans Duniter v2 — celui qui fait tourner Ğ1 depuis mars 2026 — il existe identity.changeOwnerKey : l’identité survit au changement de clé, mais tu signes la migration avec la nouvelle clé et elle reste sur la chaîne, avec une fenêtre pendant laquelle l’ancienne clé peut encore la révoquer. C’est exactement le contraire de se cacher derrière un hachage : c’est un acte public, avec des témoins.
La réponse n’est donc pas de cacher la clé : c’est de la séparer. Une clé pour signer, une autre pour garder. Que celle qui t’identifie n’ait aucune valeur, et que celle qui a de la valeur ne serve presque jamais. Dans le protocole, cela existe déjà (contrats à hiérarchie de clés, sessions qui expirent, et la voie hash-only qu’Ethereum emprunte). Dans l’expérience utilisateur, cela n’a pas encore de forme — et c’est là que nos projets sont, au fond, une expérience.
Un bunker suppose que la clé n’est qu’un coffre. Quand la clé ouvre aussi la porte de ta maison, la stratégie de long terme n’est pas de déménager : c’est d’en avoir deux.
Étape 5 : accepte la réalité

L’enquête de référence est menée par William Gasarch tous les sept ans, et le résultat est stable : en 2002, 61 personnes sur 100 croyaient que P ≠ NP. En 2012, 126 sur 152 (83 %). En 2019, 109 sur 124 (88 %). La croyance dominante est forte, mais remarque qu’elle n’est pas unanime, et que parmi les rares qui parient sur P = NP il y a des gens sérieux.
Plus intéressant que le pourcentage : pourquoi il n’y a pas de démonstration. Et là, la théorie de la complexité a une réponse inhabituellement concrète : les barrières. Il y en a trois, et elles sont démontrées :
- Relativisation (Baker, Gill et Solovay, 1975) : il existe des oracles qui rendent P = NP et des oracles qui rendent P ≠ NP. Toute technique qui fonctionne pareil avec ou sans oracle — la diagonalisation, par exemple — ne peut pas trancher la question.
- Preuves naturelles (Razborov et Rudich, 1997) : la grande méthode pour démontrer des impossibilités sur les circuits possède une propriété qui, si elle est satisfaite à la lettre, casserait aussi la cryptographie que nous croyons sûre. Prouver P ≠ NP avec ces outils serait prouver quelque chose qui impliquerait la fausseté d’une croyance que personne ne veut abandonner.
- Algébrisation (Aaronson et Wigderson, 2009) : la technique qui surmonte les deux précédentes est elle aussi bloquée, par une version algébrique de l’argument des oracles.
Traduit : ce n’est pas que personne n’a trouvé la démonstration. C’est que les techniques connues sont formellement écartées, et chacune l’a été par un théorème. C’est pour cela que P vs NP est différent des autres problèmes ouverts : la difficulté n’est pas l’absence de tentatives, elle est que nous savons que les tentatives d’un certain type ne marcheront pas.
Et il y a un pli plus inconfortable : il est concevable — non démontré, concevable — que P ≠ NP soit indépendant de ZFC, c’est-à-dire que ni la proposition ni sa négation ne puissent être démontrées avec les axiomes standards des mathématiques. Dans l’enquête de 2012, 3 % ont choisi cette option. Il existe des résultats conditionnels (Ben-David et Halevi, 1992) montrant que, sous certaines hypothèses de dureté cryptographique, P ≠ NP serait indémontrable dans des fragments faibles de l’arithmétique. Ce n’est pas un fantasme de café : c’est une possibilité que des gens sérieux notent.
Cela signifie-t-il que le domaine est gelé ? Non. En 2025, Ryan Williams a démontré que toute machine de Turing multi-rubans qui tourne en temps t peut être simulée en espace O(√t · log t) — la première amélioration substantielle en 50 ans sur le résultat de Hopcroft, Paul et Valiant (1975). C’est un résultat sur l’espace autour du mur : la relation entre temps et mémoire, les limites du calcul en général. Le problème du million reste intact, et la théorie continue d’avancer.
Étape 6 : encaisse ton million (ou renonce comme tout le monde)

Disons que tu as la démonstration demain. Est-ce que tu es payé ?
Les règles du Clay, révisées en 2018, ont trois conditions : la preuve doit être publiée dans un « Qualifying Outlet », au moins deux ans doivent s’être écoulés depuis la publication, et la solution doit avoir obtenu une acceptation générale dans la communauté mathématique. C’est seulement alors que le comité décide si cela vaut la peine de l’analyser. Les envois directs ne sont pas acceptés. La raison des deux ans n’est pas de la bureaucratie : c’est de l’expérience accumulée.
Et nous avons le cas d’étude parfait, de l’année dernière. En 2025, la revue Frontiers of Computer Science (Springer) a publié un article intitulé « SAT Requires Exhaustive Search », dont l’auteur est Deputy Editor-in-Chief de cette même revue, avec un résultat plus fort que P ≠ NP. Le commentaire technique d’Eric Allender et Ryan Williams a montré que la borne inférieure du théorème principal contredit un algorithme vieux de vingt ans de Williams, qui tourne en temps O(d^(0.8n)) dans le cas même que l’article déclare impossible. Ils ont recommandé de rétracter l’article. Le rédacteur en chef a refusé, disant ne trouver aucune preuve de faute ; le commentaire a paru avec son paragraphe final coupé. Autrement dit : une démonstration de P ≠ NP, publiée dans une revue indexée, avec un éditeur de la revue elle-même comme auteur, a passé la relecture par les pairs et elle est toujours là. C’est exactement ce que les deux ans et l’« acceptation générale » existent pour filtrer.
Et les démonstrations assistées par machine ? En juin 2026, un travail est apparu sur arXiv, formalisant en Lean 4 un théorème nommé p_equals_np : 36 fichiers, près de trois mille cibles de compilation, zéro sorry. La chaîne est : le problème d’appartenance au polytope de pedigree est polynomial, le TSP symétrique se réduit à ce problème via la formulation d’insertion multi-étapes, et donc P = NP.
Ici il faut être précis, parce que sur ce blog nous avons déjà raconté comment Lean a sécurisé le circuit d’Ironwood et nous ne voulons pas dire deux choses différentes : Lean ne vérifie pas que les mathématiques sont les bonnes : il vérifie que la conclusion découle des hypothèses que tu lui as données. Ce n’est pas un oracle de vérité, c’est le remplacement de l’erreur humaine dans une chaîne de déductions. Tout le poids reste sur l’étape qui n’est pas mécanisée : que la formulation d’insertion multi-étapes soit une réduction valide du TSP, et que la définition du polytope soit bien celle que l’article annonce. Un théorème impeccable est aussi solide que la modélisation qui le nourrit — et arXiv, contrairement à un Qualifying Outlet, ne relit rien.
C’est la même asymétrie que celle de cet article, retournée : vérifier est facile, modéliser ne l’est pas.
Le coffre

La dernière planche laisse une image plus intelligente qu’elle n’en a l’air : le million de dollars du Clay Institute est toujours intact, attendant dans un coffre dont le mot de passe est facile à vérifier mais apparemment impossible à résoudre. Le coffre est lui-même le théorème. C’est l’asymétrie transformée en objet.
Et cette asymétrie est ce qui soutient tout ce que nous racontons dans cette série. La preuve à divulgation nulle de connaissance avec laquelle Zcash sécurise un pool se vérifie en millisecondes et se produit en minutes : nous utilisons l’écart exprès, en notre faveur. PeerDAS ne télécharge pas le bloc : il échantillonne quelques cellules et il sait. La toile de confiance de Ğ1 ne demande pas la vérité complète : elle demande cinq signatures qui expirent et se renouvellent. Dans les trois cas, le même geste épistémique est fait — il n’est pas nécessaire de tout avoir pour savoir que c’est bon — et dans les trois cas, quelqu’un exploite une asymétrie entre produire et contrôler.
C’est pour cela que P vs NP n’est pas une devinette de mathématiciens. C’est la question sur le type de monde que nous habitons : un monde où croire est moins cher que savoir, et où cette remise se fabrique à volonté, ou un monde où le raccourci de la vérification peut être défait à l’envers et où tout ce qui est stocké reste à la vue de tous.
Nous ne savons pas lequel des deux est le nôtre. Nous avons parié le système financier, les communications, les identités et les clés de tes fonds qu’il s’agit du premier. Jusqu’ici, le coffre a tenu.
Le million est toujours dedans. Et la question reste ouverte, comme sur la première planche : si vérifier est bon marché, pourquoi résoudre doit-il être cher ?