Algorithme rho de Pollard

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche

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) 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 (en). Ils ont utilisé une version modifiée de l'algorithme, qui 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[réf. nécessaire].

Algorithme[modifier | modifier le code]

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

Principe mathématique[modifier | modifier le code]

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 de 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 . On peut alors recommencer en changeant la valeur de ou la fonction .

Algorithme[modifier | modifier le code]

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

entrée : un entier n composé, qui n'est 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 [2], 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

Exemple[modifier | modifier le code]

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

i xi x2i pgcd(xix2i, 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[modifier | modifier le code]

Performances[modifier | modifier le code]

L'algorithme est 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[modifier | modifier le code]

Pour f, nous choisissons un polynôme avec coefficients entiers. Les plus communs sont de la forme :

Pour certains f, l'algorithme ne trouvera pas de facteur. Si pgcd(|xaxb|, n) = n, l'algorithme échouera, parce que xa = xb, 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[modifier | modifier le code]

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

  • etc.
  • 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 264 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[modifier | modifier le code]

(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, no 3,‎ , p. 331–334 (ISSN 1572-9125, DOI 10.1007/BF01933667, lire en ligne, consulté le 11 octobre 2019)
  2. a et b Handbook of Applied Cryptography, by Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone, p. 125, describes this algorithm and others

Voir aussi[modifier | modifier le code]