Algorithme p-1 de Pollard

Cet article ne cite pas suffisamment ses sources (juillet 2018).

Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».

En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?

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

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.

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.

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.

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

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

• Algorithme rho de Pollard
• Factorisation en courbe elliptique de Lenstra
• Algorithme p+1 de Williams (en)

• Portail de la cryptologie
• Portail de l'informatique théorique
• Arithmétique et théorie des nombres