D'abord, on peut tester raisonnablement rapidement si un nombre est premier, et surtout on ne fait pas ça en factorisant le nombre, car c'est très coûteux (cf en dessous). On utilise un test de primalité genre Miller-Rabin.
De plus, pour le problème qui nous intéresse, on sait qu'une partie de la clé RSA (la partie intéressante) est un produit de deux nombres premiers. Il suffit donc de trouver un diviseur de la clé, sans se soucier si ce diviseur est premier. Bien entendu, c'est tout aussi coûteux.
L'algorithme proposé dans le post auquel tu réponds est effectivement mal évalué, mais ça n'a aucun rapport avec ton argument incorrect. Si on divise un nombre par un autre, le temps de calcul naïf est en (log n)^2, où n désigne le plus grand des deux nombres. Pour tester naïvement si un nombre est premier (et non pas pour le décomposer en facteurs, mais on s'en fout pour RSA), il faut donc en gros sqrt(n)(log n)^2 opérations. Le gros problème, c'est que dans cette analyse, n désigne la VALEUR de la clé, pas son nombre de bits. Or, pour une clé de p bits, la valeur de la clé est au minimum de 2^{p-1}. On a donc une complexité qui est bien exponentielle avec le nombre de bits de la clé. D'ailleurs on ne sait pas faire mieux, cf le post de CNS plus bas.
Enfin, je te conseille vivement la lecture d'un bon cours d'informatique, car les problèmes NP et NP-complets ne sont pas définis comme non polynomiaux, vu qu'il s'agit seulement d'une conjecture. La définition est assez technique et je ne vois pas trop l'intérêt de la donner ici, mais bon, ce n'est pas non polynomial.
[^] # Re: Un peu de maths [correction]
Posté par boubou . En réponse à la dépêche Le RSA en danger. Évalué à 6.
D'abord, on peut tester raisonnablement rapidement si un nombre est premier, et surtout on ne fait pas ça en factorisant le nombre, car c'est très coûteux (cf en dessous). On utilise un test de primalité genre Miller-Rabin.
De plus, pour le problème qui nous intéresse, on sait qu'une partie de la clé RSA (la partie intéressante) est un produit de deux nombres premiers. Il suffit donc de trouver un diviseur de la clé, sans se soucier si ce diviseur est premier. Bien entendu, c'est tout aussi coûteux.
L'algorithme proposé dans le post auquel tu réponds est effectivement mal évalué, mais ça n'a aucun rapport avec ton argument incorrect. Si on divise un nombre par un autre, le temps de calcul naïf est en (log n)^2, où n désigne le plus grand des deux nombres. Pour tester naïvement si un nombre est premier (et non pas pour le décomposer en facteurs, mais on s'en fout pour RSA), il faut donc en gros sqrt(n)(log n)^2 opérations. Le gros problème, c'est que dans cette analyse, n désigne la VALEUR de la clé, pas son nombre de bits. Or, pour une clé de p bits, la valeur de la clé est au minimum de 2^{p-1}. On a donc une complexité qui est bien exponentielle avec le nombre de bits de la clé. D'ailleurs on ne sait pas faire mieux, cf le post de CNS plus bas.
Enfin, je te conseille vivement la lecture d'un bon cours d'informatique, car les problèmes NP et NP-complets ne sont pas définis comme non polynomiaux, vu qu'il s'agit seulement d'une conjecture. La définition est assez technique et je ne vois pas trop l'intérêt de la donner ici, mais bon, ce n'est pas non polynomial.