Factorisation et nombre d'opérations

[invite18cff193]

Bonjour,

À ceux qui s'y connaissent bien dans les algorithmes de factorisation j'aimerais avoir une réponse à cette question.
En utilisant le meilleur algorithme de factorisation combien d'opérations sont nécessaires pour factoriser le nombre n=5133257 ?
Je ne cherche pas à connaître le temps nécessaire mais le déroulement des opérations en appliquant le meilleur algorithme. Dans le détail (multiplier, diviser, chercher la racine carrée, calculer un modulo etc...)
Le but est de comparer.

Merci pour toute aide.
-----

[invite18cff193]

Salut,

J'ai fait quelques recherches sur internet et je suis tombé sur un document intéressant :
http://math.univ-lyon1.fr/~roblot/re...s_partie_4.pdf

Avec la méthode Pollard amélioré la solution pour le nombre n=127199 apparaît à la 20ème itération.
Avec ma méthode (perfectible d'ailleurs), j'arrive à la solution à la 11ème itération en manipulant des nombres de taille bien inférieure à celle de Pollard.

Il y a sûrement des méthodes qui le font en moins de 11 itérations, je suppose.
Merci de me les faire connaître, je vous en serais très reconnaissant.

[invitebe0cd90e]

Salut,

Il est difficile de répondre precisement a cette question. D'abord ca n'a pas vraiment de sens en général de chercher a compter le nombre "exact" d'operation, on regardera plutot une estimation (plus precisement, la complexité des algorithmes est donnée en "grand O" de quelque chose). C'est d'autant plus vrai pour Pollard qui est un algorithme probabiliste.

Ensuite il n'y pas vraiment de meilleur algorithme, ca va dependre du nombre que tu consideres. Par exemple Pollard est tres efficace pour les nombres ayant des petits facteurs premiers. A ma connaissance l'algorithme generique le plus efficace est le suivant : http://fr.wikipedia.org/wiki/Algorit...res_généralisé

[invite18cff193]

Merci pour le commentaire utile à plus d'un titre.
Va falloir que je revois mon algo : très efficace dans la plupart des cas mais d'une totale inutilité dans certains (plus lourd que le trial division).
Y a encore des trucs à régler.

[A voir en vidéo sur Futura]