Voir la source de Algorithme p-1 de Pollard

{{À sourcer|date=juillet 2018}}

En [[théorie des nombres]], l''''algorithme ''p ''– 1 de Pollard''' est un [[algorithme]] de [[décomposition en produit de facteurs premiers]], conçu par [[John M. Pollard]] en [[1974]]. C’est un algorithme spécifique (par opposition à généraliste) car il ne fonctionne qu'avec des [[Entier naturel|entier]]s dont les facteurs possèdent une forme particulière ; c'est l'exemple le plus simple d'algorithme de factorisation en [[arithmétique modulaire]].

Les facteurs qu'il trouve sont ceux dont le précédent, ''p'' - 1, est superlisse (ou [[Entier friable#Entier ultrafriable|ultrafriable]]).

== Principe ==
Soit ''n ''un entier divisible par un [[nombre premier]] ''p'', avec ''n ''≠ ''p''. D'après le [[petit théorème de Fermat]], on a

:<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 ''M ''de ''p ''– 1, on a
{{retrait|<math>a^M \equiv 1\pmod{p}</math>}}car <math>a^{k(p-1)} \equiv ({a^{p-1}}) ^k \equiv 1^{k} \equiv 1 \mod p</math>.

Si ''p ''– 1 est ''B''-superlisse pour un certain seuil ''B'', alors ''p ''– 1 divise le [[plus petit commun multiple]] des entiers de 1 à ''B''. Donc, si l'on pose ''M ''= ppcm(1, … , ''B''), on a
:<math> a^M \equiv 1 \pmod{p}</math> pour tout ''{{math|a}} ''premier avec ''p''.
Autrement dit, ''p ''divise ''a''<sup>''M''</sup> − 1 et donc le [[PGCD|pgcd]] de ''n ''et ''a''<sup>''M''</sup> − 1 est supérieur ou égal à ''p''.
En revanche, il est possible que ce pgcd soit égal à ''n ''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 distincts et ''r'' est un nombre entier, tels que ''p'' − 1 est ''B''-superlisse et ''q'' − 1 n’est pas ''B''-superlisse. Alors pgcd(''a''<sup>''M''</sup> − 1, ''n'') fournit un facteur propre de ''n''.

On peut noter que dans le cas où ''q'' − 1 est ''B''-superlisse, le pgcd peut produire un facteur trivial parce que ''q'' divise ''a''<sup>''M''</sup> − 1.

On peut remarquer que c’est cette propriété qui rend l’algorithme spécifique. Par exemple, 172189 = 421 × 409. Or 421 − 1 = 2{{exp|2}}×3×5×7 et 409 − 1 = 2{{exp|3}}×3×17. Ainsi, une valeur appropriée pour ''B'' serait comprise entre 7 et 16. Si on avait sélectionné ''B'' inférieur à 7, le pgcd aurait valu 1, et si on avait sélectionné ''B'' supérieur à 16, le pgcd aurait été ''n''. Bien sûr, on ne peut savoir à l'avance quelle valeur de ''B'' sera appropriée, ce sera donc un facteur à prendre en compte dans l’algorithme.

Pour accélérer les calculs, on sait aussi qu'il est possible, pour calculer le pgcd, de réduire ''a''<sup>''M''</sup> − 1 modulo ''n'' :
pgcd(''a''<sup>''M''</sup> − 1, ''n'') = pgcd(''a''<sup>''M''</sup> − 1 mod ''n'', ''n''). On peut le calculer efficacement 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 '''échec'''

# sélectionner un seuil de friabilité ''B''
# prendre un ''a'' aléatoirement dans <math>(\mathbb{Z}/n\mathbb{Z})^*</math> (note : nous pouvons d’ores 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 ''a{{exp|M}}'' mod ''n'')
# <math>g \leftarrow \operatorname{pgcd}(a-1,n)</math>
# si 1 < ''g < n ''alors retourner ''g''
# si ''g ''= 1 alors sélectionner un ''B ''plus grand et aller à l’étape 2 ou retourner {{souligner|échec}}
# si ''g = n ''alors aller à l’étape 2 ou retourner {{souligner|échec}}

Si l'on obtient ''g ''= 1 à l’étape 6, cela signifie que parmi tous les ''p ''– 1 il n’y en avait aucun qui était ''B''-superlisse. Si l'on obtient ''g = n ''à l’étape 7, cela indique généralement que tous les facteurs étaient ''B''-superlisses, mais dans de rares cas, cela pourrait indiquer que ''a ''possède un petit ordre modulo ''p''.

== 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''-superlisse et ''B'' < ''q'' ≤ ''B''’, où ''q'' est un nombre premier et ''B''’ est appelée une borne semi-lisse.

Cette variante peut s'appliquer à partir de l’étape 6 de l'algorithme de base, si l'on trouve pgcd = 1 mais que l'on ne souhaite pas augmenter ''B''. Pour tous les nombres premiers {{nobr|''B'' < ''q''<sub>1</sub>, …, ''q''<sub>''L''</sub> ≤ ''B''’,}} on vérifie si

:<math>\operatorname{pgcd}\left(a^{q_iM}-1, n\right) \neq 1</math>

pour obtenir un facteur non-trivial de ''n''. Cela s'accomplit rapidement, car si on a ''c'' = ''a''<sup>''M''</sup>, ''d''<sub>1</sub> = ''q''<sub>1</sub> et ''d''<sub>''i''</sub> = ''q''<sub>''i''</sub> − ''q''<sub>''i'' − 1</sub>, alors on peut 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{{exp|2}}''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 ''p ''tel que ''p ''– 1 soit ''B''-superlisse. En conséquence, les systèmes de [[chiffrement à clé publique]] fondés sur la difficulté de la factorisation, comme [[Rivest Shamir Adleman|RSA]], imposent d'utiliser des nombres premiers n'ayant pas cette propriété pour un seuil ''B ''trop petit<ref name = "boyer">{{Ouvrage|langue=fr|auteur1=Pascal Boyer|titre=Petit compagnon des nombres et de leurs applications|lieu=Paris/58-Clamecy|éditeur=Calvage et Mounet|année=2019|pages totales=648|passage=529-534|isbn=978-2-916352-75-6|partie=VI. Cryptographie|numéro chapitre=4.|titre chapitre=RSA}}.</ref>.

== Références ==
{{Références}}

==Voir aussi==
*[[Algorithme rho de Pollard]]
*[[Factorisation en courbe elliptique de Lenstra]]
*{{Lien|trad=Williams's p + 1 algorithm|fr=Algorithme p+1 de Williams|lang=en}}

{{Portail|Cryptologie|informatique théorique|arithmétique}}

[[Catégorie:Algorithme de factorisation des entiers]]