Je me permet de te reprendre puisque tu m'y autorise ;-) .
Pour factoriser naïvement un nombre N, il faut avoir prealablement factoriser les N-1 nombres precedents, parce que sinon, tu ne peux pas decomposer les nombres en facteurs premiers puisque tu n'a pas appliquer de test total de primalité sur ces nombres. Donc la factorisation d'un nombre N se fait en O( N^N ).
La solution erronée que tu proposais, etait en temps polynomial ce qui est aujourd'hui peu couteux, alors que la borne que je t'expose est plus que polynomiale ; c'est d'ailleurs comme ça que l'on definit les problemes NP & NP-complets, ce sont les problemes qui se traitent en un temps plus que polynomial.
[^] # Re: Un peu de maths [correction]
Posté par Mouns . En réponse à la dépêche Le RSA en danger. Évalué à 3.
Pour factoriser naïvement un nombre N, il faut avoir prealablement factoriser les N-1 nombres precedents, parce que sinon, tu ne peux pas decomposer les nombres en facteurs premiers puisque tu n'a pas appliquer de test total de primalité sur ces nombres. Donc la factorisation d'un nombre N se fait en O( N^N ).
La solution erronée que tu proposais, etait en temps polynomial ce qui est aujourd'hui peu couteux, alors que la borne que je t'expose est plus que polynomiale ; c'est d'ailleurs comme ça que l'on definit les problemes NP & NP-complets, ce sont les problemes qui se traitent en un temps plus que polynomial.