Algorithme p-1 de Pollard

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Cet article ou cette section concernant les mathématiques doit être recyclé. (indiquez la date de pose grâce au paramètre date)

Une réorganisation et une clarification du contenu est nécessaire. Discutez des points à améliorer en page de discussion.

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 Michael Pollard (de) en 1974. C’est un algorithme spécifique (par opposition à généraliste) car il ne marche 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[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 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]