Algorithme p-1 de Pollard

Algorithme p-1 de Pollard

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

Sommaire

Friabilité

La friabilité — en anglais smoothness — d'un nombre entier n 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-friable si tous ses diviseurs premiers sont plus petit que le seuil B. Assez naturellement, cette notion se retrouve dans plusieurs algorithmes de factorisation --- on peut considerer 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-superfriable si toutes ses diviseurs de la forme pi, p premier et i entier, sont inferieurs à B. (Le terme superfriable a été inventé pour les besoins de cet article, faute de connaître l'équivalent usuel en français de l'anglais powersmooth.)

Principe

Soit n un entier divisible par un nombre premier p, avec n\neq p. 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} car a^{k(p-1)} - 1 = (a^{p-1}-1)\sum_{i=0}^{k-1} a^{i(p-1)}.

Si p − 1 est B-superfriable pour un certain seuil B, alors p − 1 divise le plus petit commun multiple des entiers de 1 à B. Donc, si on pose M = ppcm (1,\dots ,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

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

Notez que dans le cas où q − 1 est à B-friables, 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. 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 sur, 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

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’ore 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-superfriable. Si g = n dans l’étape 7, cela indique généralement que tous les facteurs étaient B-superfriables, mais dans de rares cas, il 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 = fqf est B-friable et B < qB’, où q est un nombre premier et B’ est appelée une borne semi-friable.

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

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


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Algorithme p-1 de Pollard de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать реферат

Regardez d'autres dictionnaires:

  • Algorithme P-1 De Pollard — 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 Pollard en 1974. C’est un algorithme spécifique, par opposition à généraliste, car il est adapté à… …   Wikipédia en Français

  • Algorithme p-1 de pollard — 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 Pollard en 1974. C’est un algorithme spécifique, par opposition à généraliste, car il est adapté à… …   Wikipédia en Français

  • Algorithme rho de Pollard — En arithmétique modulaire, l algorithme rho de Pollard est un algorithme de décomposition en produit de facteurs premiers spécifique qui est seulement effectif pour factoriser les entiers avec de petits facteurs. Il fut conçu par John M.… …   Wikipédia en Français

  • Pollard — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Pollard est un patronyme pouvant désigner : Alfred William Pollard (1859 1944), bibliographe et bibliothécaire britannique. Pollard Berrier, chanteur …   Wikipédia en Français

  • Algorithme de factorisation de nombre premier — Décomposition en produit de facteurs premiers En mathématiques et plus précisément en arithmétique modulaire, la décomposition en produit de facteurs premiers (aussi connue comme la factorisation entière en nombres premiers) est le problème… …   Wikipédia en Français

  • Algorithme Rho De Pollard — En arithmétique modulaire, l algorithme Rho de Pollard est un algorithme de décomposition en produit de facteurs premiers spécifique qui est seulement effectif pour factoriser les entiers avec de petits facteurs. Il fut conçu par John M. Pollard… …   Wikipédia en Français

  • Algorithme rho de pollard — En arithmétique modulaire, l algorithme Rho de Pollard est un algorithme de décomposition en produit de facteurs premiers spécifique qui est seulement effectif pour factoriser les entiers avec de petits facteurs. Il fut conçu par John M. Pollard… …   Wikipédia en Français

  • Algorithme ρ de Pollard — Algorithme rho de Pollard En arithmétique modulaire, l algorithme Rho de Pollard est un algorithme de décomposition en produit de facteurs premiers spécifique qui est seulement effectif pour factoriser les entiers avec de petits facteurs. Il fut… …   Wikipédia en Français

  • Algorithme Du Lièvre Et De La Tortue — Pour les articles homonymes, voir Le Lièvre et la tortue. L algorithme de Floyd de détection de cycle, encore connu sous le nom d algorithme du lièvre et de la tortue, est un algorithme pour détecter les cycles dans des séquences arbitraires, qu… …   Wikipédia en Français

  • Algorithme de Floyd de détection de cycle — Algorithme du lièvre et de la tortue Pour les articles homonymes, voir Le Lièvre et la tortue. L algorithme de Floyd de détection de cycle, encore connu sous le nom d algorithme du lièvre et de la tortue, est un algorithme pour détecter les… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”