Algorithme p-1 de Pollard

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

${\displaystyle a^{p-1}\equiv 1{\pmod {p}}}$ 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 ${\displaystyle a^{M}\equiv 1{\pmod {p}}}$car ${\displaystyle a^{k(p-1)}\equiv ({a^{p-1}})^{k}\equiv 1^{k}\equiv 1\mod p}$.

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

${\displaystyle a^{M}\equiv 1{\pmod {p}}}$ pour tout a premier avec p.

Autrement dit, p divise a^M − 1 et donc le pgcd de n et a^M − 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^M − 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^M − 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²×3×5×7 et 409 − 1 = 2³×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^M − 1 modulo n : pgcd(a^M − 1, n) = pgcd(a^M − 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

1. sélectionner un seuil de friabilité B
2. prendre un a aléatoirement dans ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{*}}$ (note : nous pouvons d’ores et déjà fixer a, une sélection aléatoire ici n’est pas impérative)
3. pour chaque nombre premier q ≤ B
   ${\displaystyle e\gets {\bigg \lfloor }{\frac {\log {B}}{\log {q}}}{\bigg \rfloor }}$
   ${\displaystyle a\gets a^{q^{e}}\mod {n}}$
   (à la fin de cette boucle, on a a^M mod n)
4. ${\displaystyle g\leftarrow \operatorname {pgcd} (a-1,n)}$
5. si 1 < g < n alors retourner g
6. si g = 1 alors sélectionner un B plus grand et aller à l’étape 2 ou retourner échec
7. si g = n alors aller à l’étape 2 ou retourner é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 B < q₁, …, q_L ≤ B’, on vérifie si

${\displaystyle \operatorname {pgcd} \left(a^{q_{i}M}-1,n\right)\neq 1}$

pour obtenir un facteur non-trivial de n. Cela s'accomplit rapidement, car si on a c = a^M, d₁ = q₁ et d_i = q_i − q_{i − 1}, alors on peut calculer

${\displaystyle a^{q_{1}M}=c^{d_{1}},a^{q_{2}M}=c^{d_{1}}c^{d_{2}}=a^{q_{1}M}c^{d_{2}},\ldots }$

Le temps d’exécution de l’algorithme avec cette variante devient alors O(B’ × log B’ × log²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 RSA, imposent d'utiliser des nombres premiers n'ayant pas cette propriété pour un seuil B trop petit^[1].