Algorithme rho de Pollard 144296 29933662 2008-05-24T09:56:13Z Mm 314 \to, pas \mapsto... En [[arithmétique modulaire]], l''''algorithme Rho de Pollard''' est un [[Algorithmique|algorithme]] de [[décomposition en produit de facteurs premiers]] spécifique qui est seulement effectif pour factoriser les [[nombre entier|entiers]] avec de petits facteurs. Il fut conçu par [[John M. Pollard]] en 1975. Il est utilisé en [[cryptologie]]. ==Définition formelle== Soit :<math>f:S\to S</math> une fonction aléatoire, et ''S'' un ensemble fini de cardinalité ''n'', où ''n'' est l'entier à factoriser. Prenons la suite : :<math>x_0,x_1,\ldots</math> définie comme : :<math>x_{i+1}=f(x_i)\hbox{ mod }n,\,x_0=2.</math> Ici, ''(mod)'' désigne la [[congruence sur les entiers]]. Comme ''S'' est un ensemble fini, la suite doit tôt ou tard se répéter. Ceci est la raison du nom de l'algorithme : la suite cyclique ressemble à la lettre grecque ρ. Maintenant, le but est de trouver ''x''<sub>''a''</sub> et ''x''<sub>''b''</sub> tel que :<math>x_a \equiv x_b \pmod{p}</math> où ''p'' est un facteur non-trivial de ''n''. Ceci voudrait dire que le pgcd(''x''<sub>''a''</sub> − ''x''<sub>''b''</sub>, ''p'') = ''p''. Comme nous ne connaissons pas ''p'', nous effectuons ces comparaisons et ces calculs [[Congruence sur les entiers|modulo]] ''n''. La recherche de ''x''<sub>''a''</sub> et ''x''<sub>''b''</sub> est une modification de l'[[Algorithme du lièvre et de la tortue|algorithme de recherche de cycle de Floyd]]. Nous exécutons deux suites définies par notre fonction aléatoire ''f'', mais nous exécutons une deux fois plus vite que l'autre. À chaque étape, nous calculons pgcd(|''x''<sub>''a''</sub>-''x''<sub>''b''</sub>|, ''n'') pour vérifier si nous avons un facteur. Si le [[PGCD|pgcd]] est plus grand que 1 et plus petit que ''n'', alors nous en avons un. ===Performances=== 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 274177 du sixième [[nombre de Fermat]] en une demie seconde. Le sixième nombre de [[Pierre de Fermat|Fermat]] est 18446744073709551617 (20 chiffres ([[décimal|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 10023859281455311421 (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 : :<math>f(x)=x^2+c\hbox{ mod }n,\,c\neq0,-2.</math> Pour certains ''f'', l'algorithme ne trouvera pas de facteur. Si pgcd(|''x''<sub>''a''</sub> − ''x''<sub>''b''</sub>|, ''n'') = ''n'', l'algorithme échouera, parce que ''x''<sub>''a''</sub> = ''x''<sub>''b''</sub>, 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. ==Exemple== Voici un exemple. Soit ''n'' = 8 051 et ''f(x)'' = ''x''<sup>2</sup> + 1 mod 8 051. {| border=1 |----- | width=30 | ''i'' || width=60 | ''x''<sub>''i''</sub> | width=60 | ''x''<sub>2''i''</sub> || pgcd(|''x''<sub>''i''</sub> − ''x''<sub>2''i''</sub>|, 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. Le succès le plus remarquable de l'algorithme rho a été la factorisation du huitième nombre de Fermat par Pollard et [[Richard Brent (scientifique)| Richard Brent]]. 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 ''F''<sub>8</sub> prend, au total, 2 heures sur un [[Univac]] 1100/42. ==Variante== L'algorithme peut être utilisé pour des recherches de [[pseudo-collision|collisions]], en particulier dans les [[fonction de hachage|fonctions de hachage]]. Soit <math>H(M_1)~</math> l'empreinte du message <math>M_1~</math>. On cherche un deuxième message <math>M_2~</math>, différent de <math>M_1~</math>, tel que <math>H(M_1)=H(M_2)~</math>. 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 <math>x~</math> dont la taille est égale à l'empreinte. On itère le hachage en calculant d'abord <math>H(x)~</math>, <math>H(H(x))~</math> 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 <math>y~</math>. On reprend le message initial <math>x~</math> et on effectue alors des itérations en parallèle sur les deux empreintes : * <math>H(x)~</math>, <math>H(H(x))~</math>, <math>H(H(H(x)))~</math>, etc. * <math>H(y)~</math>, <math>H(H(y))~</math>, <math>H(H(H(y)))~</math>, 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]] qui visait à trouver une collision complète (128 bits, complexité de 2<sup>64</sup> 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). == Voir aussi == [[Méthode des Kangourous de Pollard]] ===Liens externes=== * {{en}} [http://members.lycos.co.uk/John_M_Pollard/nthy.html Page de John Pollard] {{Portail cryptologie}} [[Catégorie:Algorithme de factorisation des entiers]] [[de:Pollard-Rho-Methode]] [[en:Pollard's rho algorithm]] [[he:אלגוריתם rho של פולרד]] [[ja:ポラード・ロー素因数分解法]] [[pl:Algorytm faktoryzacji rho Pollarda]] [[ru:Ρ-алгоритм Полларда]]