Algorithme heuristique et probabiliste de factorisation d'entiers qui utilise une suite pseudo-aléatoire dans Z/nZ, la détection de cycles et des calculs de gcd pour extraire un facteur non trivial.

Principe

Générer une suite x_{i+1} = f(x_i) mod n pour un polynôme f (souvent x^2 + c), détecter une collision ou un cycle court, puis calculer gcd(|x_i - x_j|, n) pour obtenir un facteur ; le hasard et le paradoxe des anniversaires rendent les collisions probables en temps sous-linéaire pour les petits facteurs.

Démonstration

Choisir f(x)=x^2+1 mod 8051, initialiser x_0=2 et utiliser la détection de cycles de Floyd ; lorsque deux itérés coïncident modulo un facteur non trivial, le gcd de leur différence avec 8051 fournit un facteur.

Mauvaise application

Considérer Rho de Pollard comme une méthode toujours rapide pour des nombres dont le plus petit facteur est très grand, ou ne pas relancer l'algorithme avec d'autres polynômes après de longues exécutions ; des choix faibles provoquent des cycles longs et des tentatives infructueuses.

Conséquence

Trouve souvent rapidement des facteurs relativement petits avec peu de mémoire ; efficace en étape intermédiaire après l'élimination des très petits facteurs par division d'essai et avant des méthodes de criblage plus lourdes.

Inversion

Remplacer l'itération pseudo-aléatoire et la détection de cycles par la collecte structurée de relations sur de nombreuses valeurs (comme dans le crible quadratique ou le crible du corps de nombres) pour cibler la structure composite globale plutôt que des facteurs uniques et petits.

Limite

Heuristique et probabiliste : les performances décroissent lorsque tous les facteurs premiers sont grands ou lorsque la fonction pseudo-aléatoire présente des cycles pathologiques ; ne remplace pas les cribles algébriques pour les grands semiprimes.

Tension sémantique

Se situe entre les méthodes par force brute et les grands cribles : plus rapide que la division d'essai pour des facteurs modérés mais conceptuellement et pratiquement distinct d'algorithmes algébriques déterministes comme NFS ou ECM.

Synthèse

Rho de Pollard transforme des collisions aléatoires dans une suite modulaire peu coûteuse en facteurs non triviaux via la détection de cycles et des gcd, offrant un outil probabiliste léger pour trouver des facteurs petits à moyens.