# 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 F$_8$ a pris, au total, 2 heures sur un Univac 1100/42.

## Algorithme
### Principe mathématique

Soit $n=pq$ un nombre entier composé, où $p$ est un facteur non-trivial inconnu, que l'algorithme essaye de déterminer. On se place dans $S=\mathbb {Z} /n\mathbb {Z}$ ; autrement dit, on est dans $\{0,\dots ,n-1\}$ et les calculs s'effectuent modulo $n$.
On fixe une fonction $f:S\to S$, par exemple $f:x\mapsto x^{2}+1$. La fonction devant être rapide à calculer et pseudo-aléatoire. On définit alors la suite $(x_{n})$ par $x_{n+1}=f(x_{n})$, où $x_{0}\in S$ est choisi de manière aléatoire. Comme la suite $(x_{n})$ 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.
On considère maintenant la suite des valeurs $x_{n}{\text{ mod }}p$. Comme $p$ est inconnu, cette suite ne peut pas être calculée explicitement. On sait 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 $x_{n}$. Si tel est le cas, il existe deux indices $i<j$ tels que $x_{i}\equiv x_{j}{\pmod {p}}$ mais $x_{i}\not \equiv x_{j}{\pmod {n}}$.
Alors $p$ divise $\mathrm {pgcd} (x_{j}-x_{i},n)$ mais $\mathrm {pgcd} (x_{j}-x_{i},n)\neq n$. Autrement dit, $\mathrm {pgcd} (x_{j}-x_{i},n)$ est un facteur non trivial de $n$.
Pour déterminer les indices $i$ et $j$, on utilise l'algorithme de Floyd pour rechercher un cycle. Il suffit alors de calculer $\mathrm {pgcd} (x_{2k}-x_{k},n)$ (pour $k\geq 1$) jusqu'à obtenir un facteur non trivial de $n$ ou bien obtenir le facteur $n$. En effet, celui-ci indique qu'on a $x_{k}=x_{2k}$, donc qu'on a terminé de parcourir le cycle des $(x_{k})$. On peut alors recommencer en changeant la valeur de $x_{0}$ ou la fonction $f$.

### Algorithme

On donne ici le pseudo-code, comme dans.
En Python après avoir importé une fonction pgcd:

### Exemple

Soit n = 8 051 et f(x) = x$^2$ + 1 mod 8 051. On prend x$_0$ = 2.
| i | x$_i$ | x$_{2i}$ | pgcd(x$_i$ − x$_{2i}$, 8051) |
| 1 | 5 | 26 | 1 |
| 2 | 26 | 7474 | 1 |
| 3 | 677 | 871 | 97 |
97 est un facteur non trivial de 8 051. Les autres valeurs de c peuvent donner le facteur 83 à la place de 97.

## Discussions
### Performances

On considère $n$ un nombre entier réel à factoriser à l'aide de l'algorithme. Soit $p$ un facteur premier de $n$, il est probable d'obtenir ce facteur $p$ après $\Theta ({\sqrt {p}})$ itérations de la boucle et on peut donc estimer de manière heuristique à l'aide du paradoxe des anniversaires la complexité de algorithme à $O({\sqrt[{4\,}]{n}})$ mais une preuve plus rigoureuse reste à apporter. L'algorithme est ainsi très rapide pour les nombres avec des petits facteurs. Par exemple, sur une station de travail à 733 MHz, une implémentation de l'algorithme rho, sans aucune optimisation, trouve le facteur 274 177 du sixième nombre de Fermat en une demi-seconde. Le sixième nombre de Fermat est 18 446 744 073 709 551 617 (20 chiffres décimaux). Néanmoins, pour un nombre semi-premier de même taille, la même station de travail prend environ 9 secondes pour trouver un facteur de 10 023 859 281 455 311 421 (le produit de 2 nombres premiers à 10 chiffres).

### Choix de f

Pour f, on choisit un polynôme avec coefficients entiers. Les plus communs sont de la forme :
$f(x)=x^{2}+c,\quad c\notin \{0,-2\}.$
Dans certains cas, l'algorithme peut échouer à trouver un facteur si pgcd(|x$_a$ − x$_b$|, n) = n, car cela indique que x$_a$ = x$_b$. Dans la majorité des cas, cette égalité engendre un cycle, qui ne mène pas à l'obtention d'un diviseur non trivial. Toutefois, même après la détection d'un cycle, il est possible que l'algorithme continue à produire de nouvelles valeurs permettant de découvrir un diviseur non trivial, comme l'illustre l'exemple suivant :
Pour n = 8 249, f(x) = x$^2$ + 1 mod 8 249 et x$_0$ = 3.
| i | x$_a$ | x$_b$ | pgcd(x$_a$ − x$_b$, n) |
| 1 | 10 | 101 | 1 |
| 2 | 101 | 3172 | 1 |
| 3 | 1953 | 610 | 1 |
| 4 | 3172 | 2664 | 1 |
| 5 | 6054 | 3721 | 1 |
| 6 | 610 | 610 | 8249 |
| 7 | 896 | 2664 | 1 |
| 8 | 2664 | 3721 | 1 |
| 9 | 2757 | 610 | 113 |

## Variante

L'algorithme peut être utilisé pour des recherches de collisions, en particulier dans les fonctions de hachage. Soit $H(M_{1})$ l'empreinte du message $M_{1}.$ On cherche un deuxième message $M_{2},$ différent de $M_{1},$ tel que $H(M_{1})=H(M_{2}).$ Grâce au paradoxe des anniversaires et avec l'aide de l'algorithme de Pollard, on peut faire cela sans consommer énormément de mémoire. Une implémentation naïve du paradoxe des anniversaires nécessiterait de stocker toutes les empreintes générées et de les comparer. L'algorithme Rho permet de s'affranchir de cette contrainte.
Pour y parvenir, on crée un message aléatoire $x$ dont la taille est égale à l'empreinte. On itère le hachage en calculant d'abord $H(x),H(H(x))$ et ainsi de suite. Le nombre d'états étant fini, cette itération va forcément entrer dans un cycle que l'on peut détecter avec les algorithmes vus ci-dessus. Une fois le cycle détecté, il faut trouver les deux messages distincts qui entrent en collision. Lorsque le cycle est détecté, on est en présence de l'empreinte $y.$ On reprend le message initial $x$ et l'on effectue alors des itérations en parallèle sur les deux empreintes :
* $H(x),H(H(x)),H(H(H(x))),$ etc.
* $H(y),H(H(y)),H(H(H(y))),$ etc.
On itère jusqu'à obtenir deux sorties identiques, signe d'une collision entre deux messages distincts. En pratique, on ne considère qu'une partie de la sortie de la fonction de hachage pour éviter des temps de calcul trop longs. Une variante pour le calcul distribué a été employée dans le cadre du projet MD5CRK (en) qui visait à trouver une collision complète (128 bits, complexité de 2$^{64}$ opérations) sur la fonction de hachage cryptographique MD5. Avec une bonne implémentation exécutée sur un seul PC, il est possible de trouver des collisions sur 69 bits consécutifs de SHA-1 en quelques jours (SHA-1 a une empreinte de 160 bits).