Algorithme Rho de Pollard

[invite0387e752]

Bonjour,
quelqu'un pourrait m'expliquer le fonctionnement de cet algorithme ? je ne le comprends pas tres bien en fait, je vois qu il marche de facon recursive, mais comment cela fonctionne avec les modulos etc.. ?
merci
-----

[invite0387e752]

De plus, j'ai trouvé cette procédure sous maple, et je ne comprend pas trop non plus, ici on aurait 3 variables modulo N qui sont itérées mais je ne vois pas trop le fonctionnement, si qqun pouvait m'aider

> pollard:=proc(N)
local rnd, a, f, x, y, i, g;
rnd:=rand(N); a:=rnd(); x:=rnd(); y:=x;
for i do
x:=x^2+a mod N; y:=(y^2+a mod N)^2+a mod N; g:=igcd(y-x,N);
if g<>1 then RETURN(g,i) fi
od
end:

[invite6b1e2c2e]

Salut,

Ca fait longtemps que je n'ai plus fait ça, donc je vais juste vous donner une bonne référence, ne me souvenant plus très précisément de l'algo et de l'idée clé qui le sous tend (pourtant c'était mon TIPE, mais c'était il y a déjà 5 ans ...)

Donc voilà, je vous recommande Cours d'Arithmétique, de Michel Demazure. Dans mes lointains souvenirs, je crois me souvenir que le début est un peu dur, quoique très bien expliqué, et que les algo sont présentés vers le milieu du bouquin. Cela dit, le prérequis théorique n'est nécessaire que pour montrer la convergence et expliciter pourquoi cet algo est efficace.

Bref, bonne lecture et bon courage,
__
rvz