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.