Accueil🇫🇷Chercher

Algorithme rho de Pollard (logarithme discret)

L'algorithme rho de Pollard a été introduit par John M. Pollard en 1978 pour résoudre le problème du logarithme discret. Il est analogue à l'algorithme rho de Pollard que le même auteur avait introduit pour résoudre le problème factorisation entière.

Principe

Considérons un groupe cyclique d'ordre engendré par . Le but est de calculer tel que , où appartient à . L'algorithme cherche des entiers , , , et tels que . Une fois de tel entier trouvé, l'inconnue est l'une des solutions de l'équation , autrement dit , où est l'inverse modulaire de .

Pour trouver les entiers , , , et l'algorithme utilise l'algorithme du lièvre et de la tortue pour trouver un cycle dans les séquences . Autrement dit les entiers , sont des valeurs prises par , et les entiers et sont les valeurs prises par , .

On définit la suite par est une fonction supposée pseudo-aléatoire : ainsi on a des chances d'entrer dans une boucle de longueur approximative après étapes[1]. Un moyen de définir une telle fonction est d'utiliser les règles suivantes : diviser en trois sous-ensembles disjoints de tailles approximativement égales : , , et . Si appartient à alors multiplier par deux et ; si alors incrémenter , si alors incrémenter .

Algorithme

Soit G un groupe cyclique d'ordre n. Soient . Soit une partition .

Soit une fonction définie par

et soient enfin les deux fonctions et définies par

La fonction g (respectivement h) permet de calculer les valeurs ai (respectivement bi). L'algorithme est le suivant :

 Entrées : : un générateur de G, : un élément de G
 Sortie : un entier x tel que x = , ou "échec"
 a0 ← 0, b0 ← 0, x0 ← 1
 i ← 1
 boucle
     xif(xi-1), 
     aig(xi-1, ai-1), 
     bih(xi-1, bi-1)
     x2if(f(x2i-2)), 
     a2ig(f(x2i-2), g(x2i-2, a2i-2)), 
     b2ih(f(x2i-2), h(x2i-2, b2i-2))
     si xi = x2i alors
         rbi - b2i
         si r = 0 retourner "échec"
         retourner r−1(a2i - ai) mod n
     sinon # xix2i
         ii+1

Exemple

Considérons par exemple le groupe engendré par 2 modulo (l'ordre du groupe est ). L'algorithme est implémenté par le programme suivant écrit en C++ :

 #include <stdio.h>
 
 const int n = 1018, N = n + 1;  /* N = 1019 -- prime     */
 const int alpha = 2;            /* generator             */
 const int beta = 5;             /* 2^{10} = 1024 = 5 (N) */
 
 void new_xab( int& x, int& a, int& b ) {
   switch( x%3 ) {
   case 0: x = x*x     % N;  a =  a*2  % n;  b =  b*2  % n;  break;
   case 1: x = x*alpha % N;  a = (a+1) % n;                  break;
   case 2: x = x*beta  % N;                  b = (b+1) % n;  break;
   }
 }
 
 int main(void) {
   int x=1, a=0, b=0;
   int X=x, A=a, B=b;
   for(int i = 1; i < n; ++i ) {
     new_xab( x, a, b );
     new_xab( X, A, B );
     new_xab( X, A, B );
     printf( "%3d  %4d %3d %3d  %4d %3d %3d\n", i, x, a, b, X, A, B );
     if( x == X ) break;
   }
   return 0;
 }

Les résultats sont les suivants (édités):

 i     x   a   b     X   A   B
------------------------------
 1     2   1   0    10   1   1
 2    10   1   1   100   2   2
 3    20   2   1  1000   3   3
 4   100   2   2   425   8   6
 5   200   3   2   436  16  14
 6  1000   3   3   284  17  15
 7   981   4   3   986  17  17
 8   425   8   6   194  17  19
..............................
48   224 680 376    86 299 412
49   101 680 377   860 300 413
50   505 680 378   101 300 415
51  1010 681 378  1010 301 416

Ce qui donne et ainsi , pour lequel est une solution comme on l'avait prévu. Comme n'est pas premier, il y a une autre solution , pour laquelle convient.

Complexité

Le temps d'exécution moyen est en . Si cet algorithme est utilisé avec l'algorithme de Pohlig-Hellman, le temps d'exécution des deux algorithmes combinés est en , où est le plus grand facteur premier de .

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Pollard's rho algorithm for logarithms » (voir la liste des auteurs).
  1. Menezes, Oorschot et Vanstone, chap. 2, Fact 2.37

Annexes

Bibliographie

  • (en) J. M. Pollard, « Monte Carlo methods for index computation (mod p) », Mathematics of Computation, vol. 32, no 143, , p. 918–924 (DOI 10.2307/2006496)
  • (en) Alfred J. Menezes, Paul C. van Oorschot et Scott A. Vanstone, Handbook of Applied Cryptography, (lire en ligne), « Chapter 3 »
  • Jean-Guillaume Dumas, Jean-Louis Roch, Éric Tannier et Sébastien Varrette, Théorie des codes : compression, cryptage, correction, Paris, Dunod, , 2e éd. (ISBN 978-2-10-059911-0, BNF 43668567, lire en ligne), p. 101-102

Articles connexes

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.