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^[1].

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^[2]. 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₈ a pris, au total, 2 heures sur un Univac 1100/42^[3].

Algorithme

Représentation de la suite (x_n) qui ressemble à la lettre grecque ρ.

Principe mathématique

Soit ${\displaystyle n=pq}$ un nombre entier composé, où ${\displaystyle p}$ est un facteur non-trivial inconnu, que l'algorithme essaye de déterminer. On se place dans ${\displaystyle S=\mathbb {Z} /n\mathbb {Z} }$ ; autrement dit, on est dans ${\displaystyle \{0,\dots ,n-1\}}$ et les calculs s'effectuent modulo ${\displaystyle n}$.

Fixons une fonction ${\displaystyle f:S\to S}$, par exemple ${\displaystyle f:x\mapsto x^{2}+1}$. La fonction devant être rapide à calculer et pseudo-aléatoire. On définit alors la suite ${\displaystyle (x_{n})}$ par ${\displaystyle x_{n+1}=f(x_{n})}$, où ${\displaystyle x_{0}\in S}$ est choisi de manière aléatoire. Comme la suite ${\displaystyle (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.

Considérons maintenant la suite des valeurs ${\displaystyle x_{n}{\text{ mod }}p}$. Comme ${\displaystyle p}$ 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 ${\displaystyle x_{n}}$. Si tel est le cas, il existe deux indices ${\displaystyle i<j}$ tels que ${\displaystyle x_{i}\equiv x_{j}{\pmod {p}}}$ mais ${\displaystyle x_{i}\not \equiv x_{j}{\pmod {n}}}$.

Alors ${\displaystyle p}$ divise ${\displaystyle \mathrm {pgcd} (x_{j}-x_{i},n)}$ mais ${\displaystyle \mathrm {pgcd} (x_{j}-x_{i},n)\neq n}$. Autrement dit, ${\displaystyle \mathrm {pgcd} (x_{j}-x_{i},n)}$ est un facteur non trivial de ${\displaystyle n}$.

Pour déterminer les indices ${\displaystyle i}$ et ${\displaystyle j}$, on utilise l'algorithme de Floyd pour rechercher un cycle. Il suffit alors de calculer ${\displaystyle \mathrm {pgcd} (x_{2k}-x_{k},n)}$ (pour ${\displaystyle k\geq 1}$) jusqu'à obtenir un facteur non trivial de ${\displaystyle n}$ ou bien obtenir le facteur ${\displaystyle n}$. En effet, celui-ci indique qu'on a ${\displaystyle x_{k}=x_{2k}}$, donc qu'on a terminé de parcourir le cycle des ${\displaystyle (x_{k})}$. On peut alors recommencer en changeant la valeur de ${\displaystyle x_{0}}$ ou la fonction ${\displaystyle f}$.

Algorithme

On donne ici le pseudo-code, comme dans ^[4].

entrée : un entier n composé, qui n'est pas une puissance d'un nombre premier
sortie : un facteur non trivial de n, ou alors une erreur
Pollard-Rho(n)    
    (a, b) := (2, 2)                 # dans [4], ils prennent x0 = 2
    répéter
           (a, b) = (f(a), f(f(b)))
           d := pgcd(a-b, n)
           si 1 < d < n
                    retourner d
           si d = n
                    erreur

En Python après avoir importé une fonction pgcd:

from math import gcd
def rho_pollard(n):
    def f(x):
        return x*x+1
    x, y, d = 2, 2, 1
    while d==1:
        x = f(x) % n
        y = f(f(y)) % n
        print (x,y)
        d = gcd(x-y, n) #pgcd(x-y, n)
    return d

Exemple

Soit n = 8 051 et f(x) = x² + 1 mod 8 051. On prend x₀ = 2.

i	xi	x2i	pgcd(xi − x2i, 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

Considérons ${\displaystyle n}$ un nombre entier réel à factoriser à l'aide de l'algorithme. Soit ${\displaystyle p}$ un facteur premier de ${\displaystyle n}$, il est probable d'obtenir ce facteur ${\displaystyle p}$ après ${\displaystyle \Theta ({\sqrt {p}})}$ itérations de la boucle et nous pouvons donc estimer de manière heuristique à l'aide du paradoxe des anniversaires la complexité de algorithme à ${\displaystyle O({\sqrt[{4\,}]{n}})}$^[5] mais une preuve plus rigoureuse reste à apporter^[6]. 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, nous choisissons un polynôme avec coefficients entiers. Les plus communs sont de la forme :

${\displaystyle f(x)=x^{2}+c,\quad c\notin \{0,-2\}.}$

Pour certains f, l'algorithme ne trouvera pas de facteur. Si pgcd(|x_a − x_b|, n) = n, l'algorithme échouera, parce que x_a = x_b, ce qui veut dire que la suite était bouclée et cela continuera tant que le travail précédent se répètera. En changeant c ou f, on peut augmenter la chance de succès. Cette situation d'échec peut survenir pour tous les nombres premiers, elle peut survenir pour certains nombres composés aussi.

Variante

L'algorithme peut être utilisé pour des recherches de collisions, en particulier dans les fonctions de hachage. Soit ${\displaystyle H(M_{1})}$ l'empreinte du message ${\displaystyle M_{1}.}$ On cherche un deuxième message ${\displaystyle M_{2},}$ différent de ${\displaystyle M_{1},}$ tel que ${\displaystyle 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 ${\displaystyle x}$ dont la taille est égale à l'empreinte. On itère le hachage en calculant d'abord ${\displaystyle 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 ${\displaystyle y.}$ On reprend le message initial ${\displaystyle x}$ et l'on effectue alors des itérations en parallèle sur les deux empreintes :

• ${\displaystyle H(x),H(H(x)),H(H(H(x))),}$ etc.
• ${\displaystyle 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⁶⁴ 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).

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Pollard's rho algorithm » (voir la liste des auteurs).

1. (en) J. M. Pollard, « A monte carlo method for factorization », BIT Numerical Mathematics, vol. 15, n^o 3,‎ 1^er septembre 1975, p. 331–334 (ISSN 1572-9125, DOI 10.1007/BF01933667, lire en ligne, consulté le 11 octobre 2019)
2. Richard P. Brent, « An improved Monte Carlo factorization algorithm », BIT, vol. 20, n^o 2,‎ juin 1980, p. 176–184 (ISSN 0006-3835 et 1572-9125, DOI 10.1007/bf01933190, lire en ligne, consulté le 22 février 2022)
3. (en) Richard P. Brent et John M. Pollard, « Factorization of the eighth Fermat number », Mathematics of Computation, vol. 36, n^o 154,‎ 1981, p. 627–630 (ISSN 0025-5718 et 1088-6842, DOI 10.1090/S0025-5718-1981-0606520-5, lire en ligne, consulté le 22 février 2022)
4. Handbook of Applied Cryptography, by Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone, p. 125, describes this algorithm and others
5. Thomas Cormen, Charles Leiserson, Ronald Rivest et Clifford Stein, Introduction à l'algorithmique (seconde édition), Dunod, 2004 (ISBN 2 10 003922 9), chap. 31.9 (« Factorisation des entiers »), p. 865-870
6. Steven D. Galbraith, Mathematics of public key cryptography, 2012 (ISBN 978-1-139-22114-6, 1-139-22114-0 et 1-107-01392-5, OCLC 793510851, lire en ligne)

Voir aussi

• Algorithme p-1 de Pollard
• Méthode des kangourous de Pollard
• Algorithme rho de Pollard pour les logarithmes

• Portail de la cryptologie