Algorithme rho de Pollard (logarithme discret)

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche

L'algorithme rho de Pollard a été introduit par John M. Pollard (en) 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.

Le but est de calculer tel que , où appartient à un groupe cyclique engendré par . L'algorithme calcule des entiers , , , et tels que . Si le groupe sous-jacent est cyclique d'ordre , est l'une des solutions de l'équation .

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 , où la fonction est supposée être pseudo-aléatoire et ainsi a des chances d'entrer dans une boucle après approximativement étapes. 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 : , , and . Si appartient à alors multiplier par deux et ; si alors incrémenter , si alors incrémenter .

Algorithme[modifier | modifier le code]

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

Soit une fonction définie par

et soient enfin les deux fonctions et définies par

L'algorithme est le suivant :

 Inputs a: un générateur de G, b: un élément de G
 Output un entier x tel que ax = b, ou "échec"

 Initialise a0 ← 0, b0 ← 0, x0 ← 1 ∈ G, 

 i ← 1
 loop
     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))

     if xi = x2i then
         rbi - b2i
         if r = 0 return "échec"
         xr−1(a2i - ai) mod p
         return x
     else # xix2i
         ii+1, 
         break loop
     end if
  end loop

Exemple[modifier | modifier le code]

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é[modifier | modifier le code]

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[modifier | modifier le code]

(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).

Annexes[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

  • (en) J. M. Pollard, « Monte Carlo methods for index computation (mod p) », Mathematics of Computation (en), 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), Dunod, , 2e éd. (ISBN 978-2-10-059911-0, lire en ligne), p. 101-102

Articles connexes[modifier | modifier le code]