Répondre

Golgup · 23-10-2009 21:33:32

Héhé' non : ]

aller, a+

yoshi · 23-10-2009 20:49:24

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 ?

@+

Golgup · 23-10-2009 20:40:30

Peut être n'as-tu pas vu cette intervention.. ^
|
|

Golgup · 23-10-2009 15:07:54

Hi

Hé pourquoi ne pas le poster dans programmation!

@+

yoshi · 23-10-2009 15:00:13

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

@+

yoshi · 23-10-2009 13:58:03

Salut,

Oui, j'avais lu.
J'avais essayé avec c=1 et c =3, c'est tout ;-)
J'ai recommencé : ça marche avec c = 5...

@+

Golgup · 23-10-2009 12:01:27

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à
+

yoshi · 23-10-2009 11:44:41

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

Golgup · 23-10-2009 11:12:22

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

yoshi · 23-10-2009 08:53:47

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.

@+

razuki · 22-10-2009 10:47:40

Bonjour,
je cherche une implémentation de l'algo " rho-pollard sans mémoire " afin de casser le log discret.(de préférence en C/C++)
Merci d'avance,
Aro

Forum de mathématiques - Bibm@th.net

Répondre

Résumé de la discussion (messages les plus récents en premier)

Pied de page des forums