Si la vérification de la solution d'un problème est dans P (polynomiale) alors sa résolution est dans NP (car il peut être résolu dans P par un machine non déterministe d'où le nom NP) ; ça c'est la définition de NP.
P=NP signifie donc que si on peut vérifier le résultat d'un problème rapidement alors on peut résoudre ce problème rapidement. Par exemple si le problème est la factorisation d'entier « Soit r un entier trouver deux entiers >1 tel que r=pq », Si je te donne la solution, un couple (p,q), vérifier que p * q = r se fait en tant polynomiale (on multiplie) donc la factorisation est dans NP et donc dans P !
Il existe des problèmes que ne sont même pas dans NP (encore plus difficile). Non seulement tu mets 6 siècle à résoudre le problème, mais en plus le seule moyen de vérifier que la solution est bonne est de re-résoudre le problème !
Les chiffrements asymétriques se basent sur le fait que l'on ne peut pas trouver en temps polynomiale la clé privée à partir de la clé publique. Considérons le problème « connaissant la clé publique, trouver la clé privée ». Calculer la clé publique à partir de la clé privée est rapide (sinon il faudrait 5 siècles pour générer le couple de clés) et donc on peut vérifier en temps polynomiale que la clé privée correspond à la clé publique.
Ainsi puisque P=NP, résoudre ce problème se fait en temps polynomiale.
Donc tous les chiffrements asymétriques sont foutus ! Et les chiffrements symétriques sont inutilisable seul en pratique. La seule solution serait la crypto quantique.
[^] # Re: Des commentaires de chercheur ?
Posté par Diagonale de Cantor (site web personnel) . En réponse au journal P=NP démontré ?. Évalué à 10.
Si la vérification de la solution d'un problème est dans P (polynomiale) alors sa résolution est dans NP (car il peut être résolu dans P par un machine non déterministe d'où le nom NP) ; ça c'est la définition de NP.
P=NP signifie donc que si on peut vérifier le résultat d'un problème rapidement alors on peut résoudre ce problème rapidement. Par exemple si le problème est la factorisation d'entier « Soit r un entier trouver deux entiers >1 tel que r=pq », Si je te donne la solution, un couple (p,q), vérifier que p * q = r se fait en tant polynomiale (on multiplie) donc la factorisation est dans NP et donc dans P !
Il existe des problèmes que ne sont même pas dans NP (encore plus difficile). Non seulement tu mets 6 siècle à résoudre le problème, mais en plus le seule moyen de vérifier que la solution est bonne est de re-résoudre le problème !
Les chiffrements asymétriques se basent sur le fait que l'on ne peut pas trouver en temps polynomiale la clé privée à partir de la clé publique. Considérons le problème « connaissant la clé publique, trouver la clé privée ». Calculer la clé publique à partir de la clé privée est rapide (sinon il faudrait 5 siècles pour générer le couple de clés) et donc on peut vérifier en temps polynomiale que la clé privée correspond à la clé publique.
Ainsi puisque P=NP, résoudre ce problème se fait en temps polynomiale.
Donc tous les chiffrements asymétriques sont foutus ! Et les chiffrements symétriques sont inutilisable seul en pratique. La seule solution serait la crypto quantique.