Algorithme p-1 de Pollard
143979
21821761
2007-10-16T16:10:26Z
Louperibot
238795
robot Modifie: [[en:Pollard's p - 1 algorithm]]
{{à recycler (mathématiques)}}
L''''algorithme <math>p-1</math> de Pollard''' est un [[Algorithmique|algorithme]] de l'[[arithmétique modulaire]] pour la [[décomposition en produit de facteurs premiers]], conçu par [[John Michael Pollard|John Pollard]] en [[1974]]. C’est un algorithme spécifique, par opposition à généraliste, car il est adapté à la factorisation de [[nombre entier|nombres entiers]] dont au moins un des facteurs a une forme particulière.
== Friabilité ==
La ''friabilité'' — en anglais ''smoothness'' — d'un nombre entier <math>n</math> est le fait de n'avoir que des « petits » nombres premiers comme facteurs. Généralement, on définit un seuil de friabilité, <math>B</math>, et un entier <math>n</math> est dit <math>B</math>-friable si tous ses diviseurs premiers sont plus petit que le seuil <math>B</math>. Assez naturellement, cette notion se retrouve dans plusieurs algorithmes de factorisation --- on peut considerer comme plus facile de trouver de petits facteurs.
La « bonne » notion de friabilité pour l'algorithme <math>p-1</math> considère toutes les puissances premières divisant <math>n</math> : l'entier <math>n</math> est dit ''<math>B</math>-superfriable'' si toutes ses diviseurs de la forme <math>p^i</math>, <math>p</math> premier et <math>i</math> entier, sont inferieurs à <math>B</math>. (Le terme ''superfriable'' a été inventé pour les besoins de cet article, faute de connaître l'équivalent usuel en français de l'anglais ''powersmooth''.)
== Principe ==
Soit <math>n</math> un entier divisible par un [[nombre premier]] <math>p</math>, avec <math>n\neq p</math>. Par le [[petit théorème de Fermat]], nous savons que
:<math>a^{p-1} \equiv 1\pmod{p}</math> pour ''a'' premier avec ''p''. Ici ''(mod)'' désigne la [[congruence sur les entiers]].
Cela implique que pour tout multiple <math>M</math> de <math>p-1</math> on a
<math>a^M-1\equiv 0\pmod{p}</math> car <math>a^{k(p-1)} - 1 = (a^{p-1}-1)\sum_{i=0}^{k-1} a^{i(p-1)}</math>.
Si <math>p-1</math> est <math>B</math>-superfriable pour un certain seuil <math>B</math>, alors <math>p-1</math> divise le [[PPCM|plus petit commum multiple]] des entiers de <math>1</math> à <math>B</math>. Donc, si on pose
<math>M = ppcm (1,\dots ,B)</math>,
on a
:<math> a^M \equiv 1 \pmod{p}</math> pour tout <math>a</math> premier avec <math>p</math>.
Autrement dit, <math>p</math> divise <math>a^M -1</math> et donc le [[PGCD|pgcd]] de <math>n</math> et <math>a^M -1</math> est supérieur ou égal à <math>p</math>.
En revanche, il est possible que ce pgcd soit égal à <math>n</math> lui-même auquel cas, on n'obtient pas de facteur non trivial.
== Exemple d'un cas particulier ==
Soit ''n'' = ''pqr'', où ''p'' et ''q'' sont des nombres premiers distinct et ''r'' est un nombre entier, tel que ''p'' − 1 est ''B''-friable et ''q'' − 1 n’est pas ''B''-friable. Maintenant, pgcd(''a''<sup>''M''</sup> − 1, ''n'') fournit un facteur propre de ''n''.
Notez que dans le cas où ''q'' − 1 est à <math>B</math>-friables, le pgcd peut produire un facteur trivial parce que ''q'' divise ''a''<sup>''M''</sup> − 1.
Notez que c’est ceci qui rend l’algorithme spécifique. Par exemple, 172189 = 421 × 409. 421 − 1 = 2<sup>2</sup>×3×5×7 et 409 − 1 = 2<sup>3</sup>×3×17. Donc, une valeur appropriée de ''B'' serait de 7 à 16. Si ''B'' était sélectionné plus petit que 7 le pgcd aurait été de 1 et si ''B'' était sélectionné plus grand que 16 le pgcd aurait été ''n''. Bien sur, nous ne connaissons pas quelle valeur de ''B'' est appropriée, donc ceci sera un facteur dans l’algorithme.
Pour accélérer les calculs, nous savons aussi qu’en prenant le pgcd nous pouvons réduire une partie modulo l’autre, donc pgcd(''a''<sup>''M''</sup> − 1, ''n'') = pgcd(''a''<sup>''M''</sup> − 1 mod ''n'', ''n''). Ceci peut être calculé de façon efficace en utilisant l’[[exponentiation modulaire]] et l’[[algorithme d'Euclide]].
== Algorithme et temps d’exécution ==
L’algorithme de base peut être écrit de la façon suivante :
:'''Entrées''' : ''n'' : un entier composé
:'''Sortie''' : un facteur non-trivial de ''n'' ou un <u>échec</u>
# sélectionner un seuil de friabilité ''B''
# prendre un ''a'' aléatoirement dans <math>(\mathbb{Z}/n\mathbb{Z})^*</math> (note : nous pouvons d’ore et déjà fixer ''a'', une sélection aléatoire ici n’est pas impérative)
# pour chaque nombre premier ''q'' ≤ ''B''<br /><math>e \gets \bigg\lfloor \frac{\log{B}}{\log{q}} \bigg\rfloor</math><br /><math>a \gets a^{q^e} \mod{n}</math> <br/>(à la fin de cette boucle, on a <math>a^M</math>)
# <math>g \leftarrow \operatorname{pgcd}(a-1,n)</math>
# si <math>1 < g < n</math> alors retourner <math>g</math>
# si <math>g = 1</math> alors sélectionner un <math>B</math> plus grand et aller à l’étape 2 ou retourner <u>échec</u>
# si <math>g = n</math> alors aller à l’étape 2 ou retourner <u>échec</u>
Si <math>g = 1</math> dans l’étape 6, ceci indique que pour tous les <math>p-1</math> il n’y en a aucun qui était <math>B</math>-superfriable. Si <math>g = n</math> dans l’étape 7, cela indique généralement que tous les facteurs étaient <math>B</math>-superfriables, mais dans de rares cas, il pourrait indiquer que <math>a</math> possède un petit ordre modulo <math>p</math> .
== Variante pour les grands nombres premiers ==
Une variante de l’algorithme de base est quelquefois utilisée. Statistiquement, il existe souvent un facteur ''p'' de ''n'' tel que ''p'' − 1 = ''fq'' où ''f'' est ''B''-friable et ''B'' < ''q'' ≤ ''B''’, où ''q'' est un nombre premier et ''B''’ est appelée une borne semi-friable.
Comme point de départ, ceci marcherait dans l’algorithme de base à l’étape 6 si nous avons rencontré pgcd = 1 mais que nous n’avons pas voulu augmenter ''B''. Pour tous les nombres premiers ''B'' < ''q''<sub>1</sub>, … , ''q''<sub>''L''</sub> ≤ ''B''’, nous vérifions si
:<math>\gcd\left(a^{q_im}-1, n\right) \neq 1</math>
pour obtenir pour un facteur non-trivial de ''n''. Ceci est accompli rapidement, parce que si nous avons ''c'' = ''a''<sup>''M''</sup>, et ''d''<sub>1</sub> = ''q''<sub>1</sub> et ''d''<sub>''i''</sub> = ''q''<sub>''i''</sub> − ''q''<sub>''i'' − 1</sub>, alors nous pouvons calculer
:<math>a^{q_1m} = c^{d_1}, a^{q_2m} = c^{d_1}c^{d_2} = a^{q_1m}c^{d_2}, \ldots</math>
Le temps d’exécution de l’algorithme avec cette variante devient alors O(''B''’ × log ''B''’ × log<sup>2</sup>''n'').
== Conséquence cryptologique ==
L’efficacité de cet algorithme est liée à la forme des nombres premiers composant l'entier à factoriser, plus précisément à l'existence d'un facteur premier <math>p</math> tel que <math>p-1</math> soit <math>B</math>-superfriable. En conséquence,
les systèmes de [[chiffrement à clé publique]] fondés sur la difficulté de la factorisation,
comme par exemple [[Rivest Shamir Adleman|RSA]],
imposent d'utiliser des nombres premiers n'ayant pas cette propriété pour un seuil <math>B</math> trop petit.
{{Portail cryptologie}}
[[Catégorie:Algorithme de factorisation des entiers]]
[[de:Pollard-p-1-Methode]]
[[en:Pollard's p - 1 algorithm]]