Va réviser tes cours de compléxité algorithmique (si tu en as suivi) : un algorithme est dit "NP-complet" si son temps de résolution est exponentiel en fonction de la taille des entrées (ici, le nombre de chiffres pour écrire l'entier à décomposer).
Un algo est dit "P-complet" si son temps de résolution varie comme un polynome de la taille des entrées.
Et va relire l'URL que tu donnes : la factorisation d'un nombre entier est "NP-complet".
Tu confonds tout : ce n'est pas parce que l'algorithme d'Euclide (celui que tu as décrit) fait sqrt(n) opérations qu'il n'est pas NP-complet.
Extrait de l'URL :
- "si par exemple n = pq est le produit de deux nombres premiers voisins, l'algorithme a une complexité exponentielle en fonction du nombre de chiffres nécessaires pour écrire n."
- "si n s'écrit avec k chiffres en base b, la complexité de cet algorithme est proportionnelle à bk/2, et est donc exponentielle en fonction de k. "
Un DEA d'informatique théorique, ça sert parfois avant de dire n'importe quoi ;-)
[^] # Re: Un nouvel algo de compression ?
Posté par Foxy (site web personnel) . En réponse à la dépêche Un nombre premier exécutable ... illégal ?. Évalué à 1.
Un algo est dit "P-complet" si son temps de résolution varie comme un polynome de la taille des entrées.
Et va relire l'URL que tu donnes : la factorisation d'un nombre entier est "NP-complet".
Tu confonds tout : ce n'est pas parce que l'algorithme d'Euclide (celui que tu as décrit) fait sqrt(n) opérations qu'il n'est pas NP-complet.
Extrait de l'URL :
- "si par exemple n = pq est le produit de deux nombres premiers voisins, l'algorithme a une complexité exponentielle en fonction du nombre de chiffres nécessaires pour écrire n."
- "si n s'écrit avec k chiffres en base b, la complexité de cet algorithme est proportionnelle à bk/2, et est donc exponentielle en fonction de k. "
Un DEA d'informatique théorique, ça sert parfois avant de dire n'importe quoi ;-)