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 avec de petits facteurs. Il fut conçu par John M. Pollard (en) en 1975.

Il est utilisé en cryptologie.

Sommaire

1 Définition formelle
- 1.1 Performances
- 1.2 Choix de f
2 Exemple
3 Variante
4 Notes et références
5 Voir aussi

Définition formelle

Soit

$f:S\to S$

une fonction aléatoire, et S un ensemble fini de cardinal n, où n est l'entier à factoriser. Prenons la suite $(x_n)_{n \in \mathbb{N}}$ définie par :

$x_{i+1}=f(x_i)\hbox{ mod }n,\,x_0=2.$

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 : Une représentation graphique plane de la suite cyclique ressemble à la lettre grecque ρ^[1]. Maintenant, le but est de trouver x_a et x_b tel que

$x_a \equiv x_b \pmod{p}$

où p est un facteur non-trivial de n. Or on a:

$x_a \equiv x_b \pmod{p} \Leftrightarrow pgcd(x_a - x_b, p) = p$

Comme p est justement le nombre recherché, nous effectuons ces comparaisons et ces calculs modulo n. En effet si $n$ n'est pas un nombre premier, alors il est de la forme $n=kp, k\in \mathbb{N^*}\backslash \{1\}$ et donc

$pgcd(x_a - x_b, p) = p \Leftrightarrow pgcd(x_a - x_b, n) = p$

Ainsi, à chaque étape, nous calculons le pgcd suivant:

y = p g c d (x a - x b, n)

Si $1 < y < n$ , alors $y$ est un facteur non trival de $n$ .

Un algorithme de recherche de cycle, tel celui de Floyd, permet d'éviter de parcourir la suite indéfiniment de manière inutile puisque une fois qu'un tour de boucle est effectué, les mêmes valeurs sont ensuite testées. Cet algorithme défini une relation entre les indices $a$ et $b$ . Pour le cas de l'algorithme de Floyd, on a $2 a = b$ .

Dans le cas où on ne trouve aucun facteur non-trivial avant de détecter le bouclage, il faut alors changer le choix de $f$ .

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 demi-seconde. Le sixième nombre de Fermat est 18446744073709551617 (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 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 :

$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.

Exemple

Voici un exemple. Soit n = 8 051 et f(x) = x² + 1 mod 8 051.

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.

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 F₈ prend, au total, 2 heures sur un Univac 1100/42.

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 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 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

↑ Cf. la visualisation dans L'algorithme de Floyd

Voir aussi

Portail de la cryptologie

Catégorie :

Algorithme de factorisation des entiers

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Algorithme rho de Pollard de Wikipédia en français (auteurs)

Игры ⚽ Нужно решить контрольную?

Regardez d'autres dictionnaires:

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 avec de petits facteurs. Il fut conçu par John M. Pollard… … Wikipédia en Français
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 avec de petits facteurs. Il fut conçu par John M. Pollard… … Wikipédia en Français
Algorithme ρ de Pollard — 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 avec de petits facteurs. Il fut… … Wikipédia en Français
Algorithme Du Lièvre Et De La Tortue — Pour les articles homonymes, voir Le Lièvre et la tortue. L algorithme de Floyd de détection de cycle, encore connu sous le nom d algorithme du lièvre et de la tortue, est un algorithme pour détecter les cycles dans des séquences arbitraires, qu… … Wikipédia en Français
Algorithme de Floyd de détection de cycle — Algorithme du lièvre et de la tortue Pour les articles homonymes, voir Le Lièvre et la tortue. L algorithme de Floyd de détection de cycle, encore connu sous le nom d algorithme du lièvre et de la tortue, est un algorithme pour détecter les… … Wikipédia en Français
Algorithme du lievre et de la tortue — Algorithme du lièvre et de la tortue Pour les articles homonymes, voir Le Lièvre et la tortue. L algorithme de Floyd de détection de cycle, encore connu sous le nom d algorithme du lièvre et de la tortue, est un algorithme pour détecter les… … Wikipédia en Français
Algorithme p-1 de Pollard — L algorithme p − 1 de Pollard est un algorithme de l arithmétique modulaire pour la décomposition en produit de facteurs premiers, conçu par John Pollard en 1974. C’est un algorithme spécifique, par opposition à généraliste, car il est adapté à… … Wikipédia en Français
Pollard — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Pollard est un patronyme pouvant désigner : Alfred William Pollard (1859 1944), bibliographe et bibliothécaire britannique. Pollard Berrier, chanteur … Wikipédia en Français
Algorithme de factorisation de nombre premier — Décomposition en produit de facteurs premiers En mathématiques et plus précisément en arithmétique modulaire, la décomposition en produit de facteurs premiers (aussi connue comme la factorisation entière en nombres premiers) est le problème… … Wikipédia en Français
Algorithme du lièvre et de la tortue — Pour les articles homonymes, voir Le Lièvre et la Tortue. L algorithme de Floyd de détection de cycle, encore connu sous le nom d algorithme du lièvre et de la tortue, est un algorithme pour détecter les cycles dans des séquences arbitraires, qu… … Wikipédia en Français

Dictionnaires et Encyclopédies sur 'Academic'

Algorithme rho de Pollard

Sommaire