Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
#2 23-10-2009 08:53:47
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 17 385
Re : implémentation de rho-pollard sans mémoire
Bonjour,
Bienvenue sur BibM@th...
Peut-être là :
http://www.beuiot.net/blog/john/?tag=rho-de-pollard
Que veut dire "sans mémoire" ?
Maintenant tu m'as mis sur une piste, ça m'intéresse, je vais essayer de le transcrire avec Python.
@+
Hors ligne
#3 23-10-2009 11:12:22
- Golgup
- Membre actif
- Inscription : 09-07-2008
- Messages : 574
Re : implémentation de rho-pollard sans mémoire
Hello,
Le principe mêmede p de pollard est utilisé pour deux trucs différents: l'un pour factoriser (voir ici trés clair: http://www.cuillerdier.fr/algorithmerhodepollard l'autre pour résoudre le log discret, celui que Aro veut, et je crois que 'sans mémoire' allusionne au fait que son besoin de stockage est constant. Alors Yoshi le quel tu vas programmer?
bye
Hors ligne
#4 23-10-2009 11:44:41
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 17 385
Re : implémentation de rho-pollard sans mémoire
Salut,
J'ai fait le premier...
Seulement, il ne trouve pas toujours la solution :
il décompose 10023859281455311421 mais pas 222119 !
De plus avec 222119 le calcul de pgcd me colle une erreur...
J'avais trouvé le site 'cuillerdier', mais il n'était pas clair (pour moi, désolé !), le wiki français sur lequel il pointait, pas plus, et je l'ai fait donc avec le wikipedia anglais !
Maintenant je vais voir cette histoire de "casser le log discret'"
@+
PS : razuki devrait aussi jeter un oeil à http://en.wikipedia.org/wiki/Pollard%27 … logarithms
Hors ligne
#5 23-10-2009 12:01:27
- Golgup
- Membre actif
- Inscription : 09-07-2008
- Messages : 574
Re : implémentation de rho-pollard sans mémoire
Re,
Si pour une fonction recurente x²+c (mod n), l'algo n'aboutit pas, il faut changer la valeur de c
Peut être le problème vient de là
+
Dernière modification par Golgup (23-10-2009 12:03:33)
Hors ligne
#7 23-10-2009 15:00:13
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 17 385
Re : implémentation de rho-pollard sans mémoire
Re,
J'ai refait le truc avec la méthode de rho pollard, variante de Richard Brent qui demande moins d'itérations :
http://www-lipn.univ-paris13.fr/~bander … facto.html
@+
Hors ligne
#10 23-10-2009 20:49:24
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 17 385
Re : implémentation de rho-pollard sans mémoire
Salut,
Mais si, j'ai vu...
Seulement la 2e méthode est 2 fois plus lente que la 1ere méthode alors qu'elle est réputée plus rapide...
0,75 s pour casser le 6e nombre de Fermat à 20 chiffres contre 0,37 s.
Ca vient de ce que je stocke tous les x_i dans une liste, pour retrouver un x_k antérieur : je suis en train de mettre au point une méthode pour trouver le bon x_k antérieur, mais ce soir, je suis nase...
Je reprendrai demain et je les publierai l'un après l'autre...
T'inquiète pas et patiente...
Ca ne va pas t'empêcher de dormir ?
@+
Hors ligne