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

On considère un groupe cyclique $G$ d'ordre $n$ engendré par $\alpha$. Le but est de calculer $\gamma$ tel que ${\alpha }^{\gamma }=\beta$, où $\beta$ appartient à $G$. L'algorithme cherche des entiers $a$, $b$, $A$, et $B$ tels que ${\alpha }^a{\beta }^b={\alpha }^A{\beta }^B$. Une fois de tels entiers trouvés, l'inconnue $\gamma$ est l'une des solutions de l'équation $(B-b)\gamma =(a-A)(\mathrm{mod}n)$, autrement dit $\gamma =(B-b{)}^{-1}(a-A)(\mathrm{mod}n)$, où $(B-b{)}^{-1}$est l'inverse modulaire de $(B-b)$.

Pour trouver les entiers $a$, $b$, $A$, et $B$ l'algorithme utilise l'algorithme du lièvre et de la tortue pour trouver un cycle dans les séquences $x_i={\alpha }^{a_i}{\beta }^{b_i}$. Autrement dit les entiers $a$, $b$ sont des valeurs prises par $a_i$, $b_i$ et les entiers $A$ et $B$ sont les valeurs prises par $a_{2i}$, $b_{2i}$.

On définit la suite $(x_i{)}_{i\in \mathbb{N}}$ par $x_{i+1}=f(x_i)$ où $f$ est une fonction supposée pseudo-aléatoire : ainsi on a des chances d'entrer dans une boucle de longueur approximative $\sqrt{\frac{\pi n}{8}}$ après $\sqrt{\frac{\pi n}{8}}$ étapes. Un moyenModèle:Référence nécessaire de définir une telle fonction est d'utiliser les règles suivantes : diviser $G$ en trois sous-ensembles disjoints de tailles approximativement égales : $S_0$, $S_1$, et $S_2$. Si $x_i$ appartient à $S_0$ alors multiplier par deux $a$ et $b$ ; si $x_i\in S_1$ alors incrémenter $a$, si $x_i\in S_2$ alors incrémenter $b$.

Algorithme

Soit Modèle:Mvar un groupe cyclique d'ordre Modèle:Mvar. Soient $\alpha ,\beta \in G$. Soit une partition $G=S_0\cup S_1\cup S_2$.

Soit une fonction $f:G\to G$ définie par

$f(x)=\{\begin{array}{cc}\beta x& x\in S_0\\ x^2& x\in S_1\\ \alpha x& x\in S_2\end{array}$

et soient enfin les deux fonctions $g:G\times \mathbb{Z}\to \mathbb{Z}$ et $h:G\times \mathbb{Z}\to \mathbb{Z}$ définies par

$\begin{array}{cc}g(x,a)& =\{\begin{array}{cc}a& x\in S_0\\ 2a(modn)& x\in S_1\\ a+1(modn)& x\in S_2\end{array}\\ h(x,b)& =\{\begin{array}{cc}b+1(modn)& x\in S_0\\ 2b(modn)& x\in S_1\\ b& x\in S_2\end{array}\end{array}$

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

 Entrées : $\alpha$: un générateur de G, $\beta$: un élément de G
 Sortie : un entier x tel que $\alpha$x = $\beta$, ou "échec"

 a0 ← 0, b0 ← 0, x0 ← 1

 i ← 1
 boucle
     xi ← f(xi-1), 
     ai ← g(xi-1, ai-1), 
     bi ← h(xi-1, bi-1)

     x2i ← f(f(x2i-2)), 
     a2i ← g(f(x2i-2), g(x2i-2, a2i-2)), 
     b2i ← h(f(x2i-2), h(x2i-2, b2i-2))

     si xi = x2i alors
         r ← bi - b2i
         si r = 0 retourner "échec"
         retourner r−1(a2i - ai) mod n
     sinon # xi ≠ x2i
         i ← i+1

Exemple

On considère par exemple le groupe engendré par 2 modulo $N=1019$ (l'ordre du groupe est $n=1018$). 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 $2^{681}{5}^{378}=1010=2^{301}{5}^{416}(\mathrm{mod}1019)$ et ainsi $(416-378)\gamma =681-301(\mathrm{mod}1018)$, pour lequel ${\gamma }_1=10$ est une solution comme on l'avait prévu. Comme $n=1018$ n'est pas premier, il y a une autre solution ${\gamma }_2=519$, pour laquelle $2^{519}=1014=-5(\mathrm{mod}1019)$ convient.

Complexité

Le temps d'exécution moyenModèle:Référence nécessaire est en $𝒪(\sqrt{n})$. Si cet algorithme est utilisé avec l'algorithme de Pohlig-Hellman,Modèle:Référence nécessaire le temps d'exécution des deux algorithmes combinés est en $𝒪(\sqrt{p})$, où $p$ est le plus grand facteur premier de $n$.

Annexes

Bibliographie

• Modèle:Article
• Modèle:Ouvrage
• Modèle:Ouvrage, Modèle:P.

Articles connexes

• Algorithme rho de Pollard
• Algorithme p-1 de Pollard
• Méthode des kangourous de Pollard