Algorithme rho de Pollard

En arithmétique modulaire, l’algorithme rho de Pollard est un algorithme de décomposition en produit de facteurs premiers spécifique qui est seulement effectif pour factoriser les entiers naturels avec de petits facteurs. Il fut conçu par John M. Pollard en 1975. Il est utilisé en cryptologie. Le succès le plus remarquable de l'algorithme rho a été la factorisation du huitième nombre de Fermat par Pollard et Brent, ce dernier ayant proposé une version améliorée de l'algorithme. Une version modifiée de l'algorithme a été utilisée et a trouvé un facteur premier inconnu précédemment. La factorisation complète de F8 a pris, au total, 2 heures sur un Univac 1100/42. vignette|Représentation de la suite (xn) qui ressemble à la lettre grecque ρ. Soit un nombre entier composé, où est un facteur non-trivial inconnu, que l'algorithme essaye de déterminer. On se place dans ; autrement dit, on est dans et les calculs s'effectuent modulo . Fixons une fonction , par exemple . La fonction devant être rapide à calculer et pseudo-aléatoire. On définit alors la suite par , où est choisi de manière aléatoire. Comme la suite prend un nombre fini de valeurs, elle finit par se répéter. C'est la raison du nom de l'algorithme : une représentation graphique de la suite cyclique ressemble à la lettre grecque ρ, voir figure ci-contre. Considérons maintenant la suite des valeurs . Comme est inconnu, cette suite ne peut pas être calculée explicitement. Nous savons qu'elle se répète également. A cause du paradoxe des anniversaires, sa période de répétition est souvent strictement plus petite que celui de la suite . Si tel est le cas, il existe deux indices tels que mais . Alors divise mais . Autrement dit, est un facteur non trivial de . Pour déterminer les indices et , on utilise l'algorithme de Floyd pour rechercher un cycle. Il suffit alors de calculer (pour ) jusqu'à obtenir un facteur non trivial de ou bien obtenir le facteur . En effet, celui-ci indique qu'on a , donc qu'on a terminé de parcourir le cycle des .