Le socle théorique

Sens unique et P vs NP

Pourquoi croit-on que factoriser est difficile ? La réponse plonge dans la théorie de la complexité, et notamment dans la plus célèbre question ouverte de l'informatique : P vs NP.

Vérifier n'est pas trouver

Considérons le problème de la factorisation. Si je vous donne n = 91 et que je prétends que 7 en est un facteur, vous vérifiez en une multiplication : 7 × 13 = 91. Facile.

Mais si je vous donne seulement n = 91 et vous demande de trouver un facteur, il faut chercher. Sur de petits nombres, cela va vite ; sur un n de 600 chiffres, aucune méthode connue n'aboutit en un temps raisonnable.

C'est la distinction fondamentale :

   +---------------------+-----------------------------+
   |  VÉRIFIER (facile)  |  TROUVER (conjecturé dur)   |
   +---------------------+-----------------------------+
   |  7 × 13 == 91 ?     |  facteur de 91 = ?          |
   |  une multiplication |  chercher parmi les diviseurs|
   +---------------------+-----------------------------+

Les classes P et NP

La théorie de la complexité range les problèmes en classes :

P : les problèmes que l'on sait résoudre rapidement (en temps polynomial).
NP : les problèmes dont une solution proposée se vérifie rapidement.

Tout problème de P est dans NP (si on sait résoudre, on sait vérifier). La grande question est la réciproque : P = NP ? Autrement dit, tout ce qui se vérifie vite peut-il aussi se résoudre vite ?

Problème	Vérifier une solution	Trouver une solution
Factoriser `n`	facile (une multiplication)	conjecturé dur
Logarithme discret	facile (une exponentiation)	conjecturé dur
Sudoku `k × k`	facile (contrôler la grille)	conjecturé dur

Le lien avec la cryptographie

Une fonction à sens unique a besoin que l'inversion soit dure alors que la vérification est facile. C'est exactement le profil d'un problème de NP qui ne serait pas dans P.

Conséquence vertigineuse : si P = NP, aucune fonction à sens unique ne pourrait exister. Tout ce qui se vérifie vite se résoudrait vite ; factoriser, inverser un logarithme discret deviendraient faciles ; RSA, Diffie-Hellman et la quasi-totalité de la cryptographie à clé publique s'effondreraient.

À l'inverse, P ≠ NP est nécessaire mais pas suffisant : même dans ce cas, il faudrait encore que nos problèmes précis (factorisation, log discret) soient effectivement durs.

Un édifice bâti sur une conjecture

La cryptographie moderne assume donc un pari : elle suppose durs quelques problèmes bien étudiés — factorisation, logarithme discret, problèmes sur les réseaux euclidiens — sans preuve absolue de leur difficulté.

Ce n'est pas une faiblesse honteuse mais un choix assumé : ces problèmes résistent depuis des décennies aux meilleurs chercheurs, ce qui constitue la meilleure garantie disponible.

En résumé