Algorithme p-1 de Pollard

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

L'algorithme p – 1 de Pollard est un algorithme de l'arithmétique modulaire pour la décomposition en produit de facteurs premiers, conçu par John Michael Pollard (de) en 1974. C’est un algorithme spécifique, par opposition à généraliste, car il est adapté à la factorisation de nombres entiers dont au moins un des facteurs a une forme particulière.

Friabilité[modifier | modifier le code]

La friabilité — en anglais smoothness — d'un nombre entier est le fait de n'avoir que des « petits » nombres premiers comme facteurs. Généralement, on définit un seuil de friabilité, B, et un entier n est dit B-lisse si tous ses diviseurs premiers sont plus petits que le seuil B. Assez naturellement, cette notion se retrouve dans plusieurs algorithmes de factorisation — on peut considérer comme plus facile de trouver de petits facteurs.

La « bonne » notion de friabilité pour l'algorithme p – 1 considère toutes les puissances premières divisant n : l'entier n est dit B-superlisse si tous ses diviseurs de la forme pk, p premier et k entier, sont inférieurs à B.

Principe[modifier | modifier le code]

Soit n un entier divisible par un nombre premier p, avec np. Par le petit théorème de Fermat, nous savons que

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 a^M-1\equiv 0\pmod{p}\text{ car }a^{k(p-1)} - 1 = (a^{p-1}-1)\sum_{i=0}^{k-1} a^{i(p-1)}.

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

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

Autrement dit, p divise aM − 1 et donc le pgcd de n et aM − 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[modifier | modifier le code]

Soit n = pqr, où p et q sont des nombres premiers distincts et r est un nombre entier, tel que p − 1 est B-lisse et q − 1 n’est pas B-lisse. Maintenant, pgcd(aM − 1, n) fournit un facteur propre de n.

Notez que dans le cas où q − 1 est B-lisse, le pgcd peut produire un facteur trivial parce que q divise aM − 1.

Notez que c’est ceci qui rend l’algorithme spécifique. Par exemple, 172189 = 421 × 409. Or 421 − 1 = 22×3×5×7 et 409 − 1 = 23×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 sûr, 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(aM − 1, n) = pgcd(aM − 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[modifier | modifier le code]

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 (\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 qB
    e \gets \bigg\lfloor \frac{\log{B}}{\log{q}} \bigg\rfloor
    a \gets a^{q^e} \mod{n}
    (à la fin de cette boucle, on a aM)
  4. 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 g = 1 dans l’étape 6, ceci indique que pour tous les p – 1 il n’y en a aucun qui était B-superlisse. Si g = n dans l’étape 7, cela indique généralement que tous les facteurs étaient B-superlisses, mais dans de rares cas, il pourrait indiquer que a possède un petit ordre modulo p.

Variante pour les grands nombres premiers[modifier | modifier le code]

Une variante de l’algorithme de base est quelquefois utilisée. Statistiquement, il existe souvent un facteur p de n tel que p − 1 = fqf est B-lisse et B < qB’, où q est un nombre premier et B’ est appelée une borne semi-lisse.

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 < q1, …, qLB’, nous vérifions si

\gcd\left(a^{q_im}-1, n\right) \neq 1

pour obtenir pour un facteur non-trivial de n. Ceci est accompli rapidement, parce que si nous avons c = aM, et d1 = q1 et di = qiqi − 1, alors nous pouvons calculer

a^{q_1m} = c^{d_1}, a^{q_2m} = c^{d_1}c^{d_2} = a^{q_1m}c^{d_2}, \ldots

Le temps d’exécution de l’algorithme avec cette variante devient alors O(B’ × log B’ × log2n).

Conséquence cryptologique[modifier | modifier le code]

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 par exemple RSA, imposent d'utiliser des nombres premiers n'ayant pas cette propriété pour un seuil B trop petit.

Voir aussi[modifier | modifier le code]