Premier point :
---------------
J'ai bien l'impression que les notions de NP etc. te posent quelques problèmes...
Commençons donc par le commencement (ça n'a rien à faire sur linuxfr, mais bon). Un problème P est un problème qu'on peut résoudre en temps polynomial, c'est-à-dire en un temps d'exécution qui dépend comme un polynome de la taille des données. Pour une définition formelle, cf http://www.claymath.org/prizeproblems/p_vs_np.pdf(...) (qui est excellent).
Deuxième définition : non-P. Un problème non-P est un problème pour lequel on sait prouver qu'il n'existe pas de résolution en temps polynomial. Il est extrêmement difficile de démontrer qu'un problème est non-P, mais ça a déjà été fait et donc on est bien entendu sûr que P /= non-P (ce qui est évident) et surtout que les deux ensembles ne sont pas vides.
Troisième définition : NP. Effectivement, NP signifie nondeterministic polynomial time, ce qui ne veut en aucun cas dire non-P. Ca veut dire polynomial sur une machine non déterministe (c'est-à-dire pas sur un ordinateur classique). La définition moderne est donnée dans l'article que j'ai cité au dessus (http://www.claymath.org/prizeproblems/p_vs_np.pdf(...)). Avec les mains, ça donne la chose suivante : un problème est NP si répondre à la question "cette donnée est elle une solution du problème ?" peut se faire en temps polynomial.
Propriété triviale : P est contenu dans NP.
Quatrième définition : NP-complet. On dit qu'un problème est NP-complet si tout problème NP peut se ramener en temps polynomial au problème étudié. En gros pour résoudre un problème NP, on bidouille l'énoncé du problème (en temps polynomial) et on donne l'énoncé bidouillé au programme qui résout le problème NP-complet : la réponse du programme est bonne pour le problème d'origine.
Bien entendu (et c'est tout l'aspect fun du problème), personne ne sait si P=NP (ou si P/=NP) (cf toujours le même papier).
Deuxième point :
----------------
Pour décomposer un nombre en facteurs premiers, il suffit d'appliquer récursivement le "cassage" à ses facteurs. J'appelle "cassage" un algorithme qui trouve un facteur non trivial d'un nombre p (i.e. différent de 1 et p). Si tu veux décomposer 20 en facteurs premiers, il te suffit de le casser, c'est-à-dire de trouver que 20=2x10 (à priori tu devrais d'abord trouver 2). Ensuite, tu casses récursivement 2 et 10 (soit 2x5) et donc 5. Moralité, tu as cassé 2,5,10 et 20, et non pas tous les nombres avants. Moralité de la moralité : arrêtes de dire des conneries.
Troisième point :
-----------------
Il existe un algorithme de cassage (cf après) polynomial, mais cet algorithme n'est juste que si la conjecture de riemann (un truc bien compliqué...) est vraie. La plupart des spécialistes pensent que la factorisation en temps polynomial est cependant peu probable. Donc ACTUELLEMENT il n'existe pas d'algo de factorisation en temps polynomial. MAIS CE N'EST PAS LE PROBLEME POUR RSA PUISQU'ON SE CONTENTE D'UN CASSAGE !!!!!!!!! Or, il se trouve qu'il n'existe pas pour l'instant d'algorithme de cassage en temps polynomial, ce qui est le bon argument pour RSA (tu fais de nouveau l'erreur pour la primalité). Bien entendu, la factorisation et le cassage sont dans NP, mais comme ils ne sont pas NP complets (enfin, on pense qu'ils ne le sont pas), les conjectures basés sur les gros problèmes NP-complets peuvent très bien ne pas s'appliquer à eux. En d'autres termes, même si tout le monde pense que les problèmes NP-complets demandent un temps exponentiel, ça n'apporte pas trop d'information sur le cassage.
Disclaimer : je suis maître de conférences en informatique. Oui, ça aide.
[^] # NP/=non-P
Posté par boubou . En réponse à la dépêche Le RSA en danger. Évalué à 6.
---------------
J'ai bien l'impression que les notions de NP etc. te posent quelques problèmes...
Commençons donc par le commencement (ça n'a rien à faire sur linuxfr, mais bon). Un problème P est un problème qu'on peut résoudre en temps polynomial, c'est-à-dire en un temps d'exécution qui dépend comme un polynome de la taille des données. Pour une définition formelle, cf http://www.claymath.org/prizeproblems/p_vs_np.pdf(...) (qui est excellent).
Deuxième définition : non-P. Un problème non-P est un problème pour lequel on sait prouver qu'il n'existe pas de résolution en temps polynomial. Il est extrêmement difficile de démontrer qu'un problème est non-P, mais ça a déjà été fait et donc on est bien entendu sûr que P /= non-P (ce qui est évident) et surtout que les deux ensembles ne sont pas vides.
Troisième définition : NP. Effectivement, NP signifie nondeterministic polynomial time, ce qui ne veut en aucun cas dire non-P. Ca veut dire polynomial sur une machine non déterministe (c'est-à-dire pas sur un ordinateur classique). La définition moderne est donnée dans l'article que j'ai cité au dessus (http://www.claymath.org/prizeproblems/p_vs_np.pdf(...)). Avec les mains, ça donne la chose suivante : un problème est NP si répondre à la question "cette donnée est elle une solution du problème ?" peut se faire en temps polynomial.
Propriété triviale : P est contenu dans NP.
Quatrième définition : NP-complet. On dit qu'un problème est NP-complet si tout problème NP peut se ramener en temps polynomial au problème étudié. En gros pour résoudre un problème NP, on bidouille l'énoncé du problème (en temps polynomial) et on donne l'énoncé bidouillé au programme qui résout le problème NP-complet : la réponse du programme est bonne pour le problème d'origine.
Bien entendu (et c'est tout l'aspect fun du problème), personne ne sait si P=NP (ou si P/=NP) (cf toujours le même papier).
Comme tu n'as pas l'air très fort, tu peux aussi lire la version pour les enfants du papier, i.e. http://www.claymath.org/prizeproblems/milliondollarminesweeper.htm(...)
Deuxième point :
----------------
Pour décomposer un nombre en facteurs premiers, il suffit d'appliquer récursivement le "cassage" à ses facteurs. J'appelle "cassage" un algorithme qui trouve un facteur non trivial d'un nombre p (i.e. différent de 1 et p). Si tu veux décomposer 20 en facteurs premiers, il te suffit de le casser, c'est-à-dire de trouver que 20=2x10 (à priori tu devrais d'abord trouver 2). Ensuite, tu casses récursivement 2 et 10 (soit 2x5) et donc 5. Moralité, tu as cassé 2,5,10 et 20, et non pas tous les nombres avants. Moralité de la moralité : arrêtes de dire des conneries.
Troisième point :
-----------------
Il existe un algorithme de cassage (cf après) polynomial, mais cet algorithme n'est juste que si la conjecture de riemann (un truc bien compliqué...) est vraie. La plupart des spécialistes pensent que la factorisation en temps polynomial est cependant peu probable. Donc ACTUELLEMENT il n'existe pas d'algo de factorisation en temps polynomial. MAIS CE N'EST PAS LE PROBLEME POUR RSA PUISQU'ON SE CONTENTE D'UN CASSAGE !!!!!!!!! Or, il se trouve qu'il n'existe pas pour l'instant d'algorithme de cassage en temps polynomial, ce qui est le bon argument pour RSA (tu fais de nouveau l'erreur pour la primalité). Bien entendu, la factorisation et le cassage sont dans NP, mais comme ils ne sont pas NP complets (enfin, on pense qu'ils ne le sont pas), les conjectures basés sur les gros problèmes NP-complets peuvent très bien ne pas s'appliquer à eux. En d'autres termes, même si tout le monde pense que les problèmes NP-complets demandent un temps exponentiel, ça n'apporte pas trop d'information sur le cassage.
Disclaimer : je suis maître de conférences en informatique. Oui, ça aide.