Page d'accueil	encyclopedie-enligne.com en page d'accueil
Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] \| Liste Catégories \| Une page au hasard \| Pages liées

Algorithme p-1 de Pollard

L'algorithme p − 1 de Pollard est un algorithme en théorie des nombres de 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

1 Concepts de base

2 Concepts de Pollard

3 Algorithme et temps d'exécution

4 Variante pour les grands nombres premiers

5 Information supplémentaire

Concepts de base

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

$a^{p-1} \equiv 1\pmod{p}$ pour $a \in (\mathbb{Z}/n\mathbb{Z})^*$

Assurons-nous que p − 1 est B-friable pour un certain B d'une taille raisonnable (plus sur la sélection de cette valeur plus tard). Rappelons ceci, un entier m est appelé B-friable si tous les facteurs premiers p_i de m sont tels que p_i ≤ B. m est appelé B-friable si toutes les puissances premières p_iⁿ divisant m sont telles que p_iⁿ ≤ B.

Soient p₁, ..., p_L les nombres premiers inférieurs à B et soient e₁, ..., e_L les exposants tels que

$p_i^{e_i} \le B < p_i^{e_i + 1}$

Soit $M = \prod_{i = 1}^{L} p_i^{e_i}$

Notons M = ppcm{1, ..., B}. Ainsi, (p − 1) divise M, et aussi si p^e divise M ceci implique que p^e ≤ B. Comme (p − 1) divise M, alors a^M ≡ 1 (mod p), et comme p divise n ceci veut dire pgcd(a^M − 1, n) > 1.

Par conséquent, si pgcd(a^M − 1, n) ≠ n, alors le pgcd est un facteur non-trivial de n.

Notez que si p − 1 n'est pas B-friable, alors a^M ≢ 1 (mod p) pour au moins la moitié de tous les a.

Concepts de Pollard

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(a^M − 1, n) fournit un facteur propre de n.

Notez que dans le cas où q − 1 est B-régulier, le pgcd peut produire un facteur trivial parceque q divise a^M − 1.

Notez que c'est ceci qui rend l'algorithme spécifique. Par exemple, 172189 = 421 × 409. 421 − 1 = 2²×3×5×7 et 409 − 1 = 2³×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(a^M − 1, n) = pgcd(a^M − 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

sélectionner un borne régulière B
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)
pour chaque nombre premier q ≤ B
$e \gets \bigg\lfloor \frac{\log{B}}{\log{q}} \bigg\rfloor$
$a \gets a^{q^e} \mod{n}$ (note : ceci est a^M)
g ← pgcd(a − 1, n)
si 1 < g < n alors retourner g
si g = 1 alors sélectionner un B plus grand et aller à l'étape 2 ou retourner échec
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-régulier. Si g = n dans l'étape 7, ceci indique généralement que tous les facteurs étaient B-réguliers, mais dans de rares cas, il pourrait indiquer que a possède un petit ordre modulo p.

Le temps d'exécution de cet algorithme est O(B × log B × log²n), donc, il est avantageux de prendre une petite valeur de B.

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-friable et B < q ≤ B', 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 < q₁, ..., q_L ≤ B', 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, parceque si nous avons c = a^M, et d₁ = q₁ et d_i = q_i − q_{i − 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' × log²n).

Information supplémentaire

Comme l'efficacité de cet algorithme est liée la forme des nombres premiers, il est requit pour RSA, des nombres premiers p et q tel que p-1 et q-1 ne soit pas B-friable pour de petites valeurs de B.

Catégories: Algorithme | Théorie des nombres

This site support the Wikimedia Foundation. This Article originally from Wikipedia. All text is available under the terms of the