Plus précisément : si P = NP et qu'on a un moyen raisonablement efficace de réduire un problème NP à un problème P, alors la plupart des algo utilises en crypto posent problème.
On considère en théorie que « polynomial = pas cher » et « exponentiel = cher », mais un algo en N^100, en pratique, c'est pas si différent d'un truc exponentiel (le comportement pour N très grand est différent, mais de toutes façons, on aura atteint les limites de la machine bien avant de s'en rendre compte).
[^] # Re: Il dit qu'il est pas d'accord.
Posté par Matthieu Moy (site web personnel) . En réponse au journal P != NP : la preuve. Évalué à 3.
On considère en théorie que « polynomial = pas cher » et « exponentiel = cher », mais un algo en N^100, en pratique, c'est pas si différent d'un truc exponentiel (le comportement pour N très grand est différent, mais de toutes façons, on aura atteint les limites de la machine bien avant de s'en rendre compte).