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.

PrincipeModifier

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 après approximativement   étapes[réf. nécessaire]. Un moyen[réf. nécessaire] 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  .

AlgorithmeModifier

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

ExempleModifier

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

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

Notes et référencesModifier

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

AnnexesModifier

BibliographieModifier

  • (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, notice BnF no FRBNF43668567, lire en ligne), p. 101-102

Articles connexesModifier