Pollard's rho algorithm for logarithms

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

Pollard's rho algorithm for logarithms is an algorithm introduced by John Pollard in 1978 to solve the discrete logarithm problem, analogous to Pollard's rho algorithm to solve the integer factorization problem.

The goal is to compute such that , where belongs to a cyclic group generated by . The algorithm computes integers , , , and such that . If the underlying group is cyclic of order , is one of the solutions of the equation .

To find the needed , , , and the algorithm uses Floyd's cycle-finding algorithm to find a cycle in the sequence , where the function is assumed to be random-looking and thus is likely to enter into a loop after approximately steps. One way to define such a function is to use the following rules: Divide into three disjoint subsets of approximately equal size: , , and . If is in then double both and ; if then increment , if then increment .

Algorithm

Let G be a cyclic group of order p, and given , and a partition , let be a map

and define maps and by

 Inputs a: a generator of G, b: an element of G
 Output An integer x such that ax = b, or failure

 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 failure
         xr−1(a2i - ai) mod p
         return x
     else # xix2i
         ii+1, 
         break loop
     end if
  end loop

Example

Consider, for example, the group generated by 2 modulo (the order of the group is , 2 generates the group of units modulo 1019). The algorithm is implemented by the following C++ program:

 #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;
 }

The results are as follows (edited):

 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

That is and so , for which is a solution as expected. As is not prime, there is another solution , for which holds.

Complexity

The running time is approximately . If used together with the Pohlig-Hellman algorithm, the running time of the combined algorithm is , where is the largest prime factor of .

References

  • Pollard, J. M. (1978). "Monte Carlo methods for index computation (mod p)". Mathematics of Computation. 32 (143): 918–924. doi:10.2307/2006496. 
  • Menezes, Alfred J.; van Oorschot, Paul C.; Vanstone, Scott A. (2001). "Chapter 3" (PDF). Handbook of Applied Cryptography. 
Retrieved from "https://en.wikipedia.org/w/index.php?title=Pollard%27s_rho_algorithm_for_logarithms&oldid=850486011"
This content was retrieved from Wikipedia : http://en.wikipedia.org/wiki/Pollard's_rho_algorithm_for_logarithms
This page is based on the copyrighted Wikipedia article "Pollard's rho algorithm for logarithms"; it is used under the Creative Commons Attribution-ShareAlike 3.0 Unported License (CC-BY-SA). You may redistribute it, verbatim or modified, providing that you comply with the terms of the CC-BY-SA