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 F8 a pris, au total, 2 heures sur un Univac 1100/42[3].
Algorithme
![](http://upload.wikimedia.org/wikipedia/commons/thumb/5/50/Pollard_rho_cycle.svg/220px-Pollard_rho_cycle.svg.png)
Principe mathématique
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 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
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) = x2 + 1 mod 8 051. On prend x0 = 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 un nombre entier réel à factoriser à l'aide de l'algorithme. Soit un facteur premier de , il est probable d'obtenir ce facteur après itérations de la boucle et nous pouvons donc estimer de manière heuristique à l'aide du paradoxe des anniversaires la complexité de algorithme à [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 :
Pour certains f, l'algorithme ne trouvera pas de facteur. Si pgcd(|xa − xb|, 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
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
- ↑ (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 )
- ↑ Richard P. Brent, « An improved Monte Carlo factorization algorithm », BIT, vol. 20, no 2, , p. 176–184 (ISSN 0006-3835 et 1572-9125, DOI 10.1007/bf01933190, lire en ligne, consulté le )
- ↑ (en) Richard P. Brent et John M. Pollard, « Factorization of the eighth Fermat number », Mathematics of Computation, vol. 36, no 154, , p. 627–630 (ISSN 0025-5718 et 1088-6842, DOI 10.1090/S0025-5718-1981-0606520-5, lire en ligne, consulté le )
- ↑ 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
- ↑ Thomas Cormen, Charles Leiserson, Ronald Rivest et Clifford Stein, Introduction à l'algorithmique (seconde édition), Dunod, (ISBN 2 10 003922 9), chap. 31.9 (« Factorisation des entiers »), p. 865-870
- ↑ Steven D. Galbraith, Mathematics of public key cryptography, (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