Page d'accueil	encyclopedie-enligne.com en page d'accueil
Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] \| Liste Catégories \| Une page au hasard \| Pages liées

Algorithme rho de Pollard

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

Soit

$f:S\mapsto S$

une fonction aléatoire, et S un ensemble fini de cardinalité n, où n est l'entier à factoriser. Prenons la suite :

$x_0,x_1,\ldots$

définie comme :

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

Comme S est un ensemble fini, la suite doit éventuellement 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_a et x_b tel que

$x_a \equiv x_b \pmod{p}$

où p est un facteur non-trivial de n. Ceci voudrait dire que le pgcd(x_a − x_b, p) = p. Comme nous ne connaissons pas p, nous effectuons ces comparaisons et ces calculs modulo n.

La recherche de x_a et x_b est une modification de l'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_a-x_b|, n) pour vérifier si nous avons un facteur. Si le pgcd est plus grand que 1 et plus petit que n, alors nous en avons un.

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

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

$f(x)=x^2+c\hbox{ mod }n,\,c\neq0,-2.$

Pour certains f, l'algorithme ne trouvera pas de facteur. Si pgcd(|x_a − x_b|, n) = n, l'algorithme échouera, parceque 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.

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

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

Catégories: Algorithme | Théorie des nombres

This site support the Wikimedia Foundation. This Article originally from Wikipedia. All text is available under the terms of the