View source for Pollard's rho algorithm for logarithms

{{Short description|Mathematical algorithm}}
'''Pollard's rho algorithm for logarithms''' is an algorithm introduced by [[Biography:John Pollard (mathematician)|John Pollard]] in 1978 to solve the [[Discrete logarithm|discrete logarithm]] problem, analogous to [[Pollard's rho algorithm]] to solve the [[Integer factorization|integer factorization]] problem.

The goal is to compute <math>\gamma</math> such that <math>\alpha ^ \gamma = \beta</math>, where <math>\beta</math> belongs to a [[Cyclic group|cyclic group]] <math>G</math> generated by <math>\alpha</math>. The algorithm computes [[Integer|integer]]s <math>a</math>, <math>b</math>,  <math>A</math>, and <math>B</math> such that <math>\alpha^a \beta^b = \alpha^A \beta^B</math>. If the underlying [[Group (mathematics)|group]] is cyclic of order <math>n</math>, by substituting <math> \beta </math> as <math> {\alpha}^{\gamma} </math> and noting that two powers are equal [[If and only if|if and only if]] the exponents are equivalent modulo the order of the base, in this case modulo <math>n</math>, we get that <math>\gamma</math> is one of the solutions of the equation <math>(B-b) \gamma = (a-A) \pmod n</math>. Solutions to this equation are easily obtained using the [[Extended Euclidean algorithm|extended Euclidean algorithm]].

To find the needed <math>a</math>, <math>b</math>,  <math>A</math>, and <math>B</math> the algorithm uses Floyd's cycle-finding algorithm to find a cycle in the sequence <math>x_i = \alpha^{a_i} \beta^{b_i}</math>, where the [[Function (mathematics)|function]] <math>f: x_i \mapsto x_{i+1}</math> is assumed to be random-looking and thus is likely to enter into a loop of approximate length <math>\sqrt{\frac{\pi n}{8}}</math> after <math>\sqrt{\frac{\pi n}{8}}</math> steps. One way to define such a function is to use the following rules: [[Partition of a set|Partition]] <math>G</math> into three disjoint subsets <math>S_0</math>, <math>S_1</math>, and <math>S_2</math> of approximately equal size using a [[Hash function|hash function]]. If <math>x_i</math> is in <math>S_0</math> then double both <math>a</math> and <math>b</math>; if <math>x_i \in S_1</math> then increment <math>a</math>, if <math>x_i \in S_2</math> then increment <math>b</math>.

==Algorithm==

Let <math>G</math> be a [[Cyclic group|cyclic group]] of order <math>n</math>, and given <math>\alpha, \beta\in G</math>, and a partition <math>G = S_0\cup S_1\cup S_2</math>, let <math>f:G\to G</math> be the map 

:<math>
f(x) = \begin{cases}
\beta x & x\in S_0\\
x^2 & x\in S_1\\
\alpha x & x\in S_2
\end{cases}
</math>

and define maps <math>g:G\times\mathbb{Z}\to\mathbb{Z}</math> and <math>h:G\times\mathbb{Z}\to\mathbb{Z}</math> by

:<math>\begin{align}
g(x,k) &= \begin{cases}
k & x\in S_0\\
2k \pmod {n} & x\in S_1\\
k+1 \pmod {n} & x\in S_2
\end{cases}
\\
h(x,k) &= \begin{cases}
k+1 \pmod {n} & x\in S_0\\
2k \pmod {n} & x\in S_1\\
k & x\in S_2
\end{cases}
\end{align}</math>

 '''input:''' ''a'': a generator of ''G''
        ''b'': an element of ''G''
 '''output:''' An integer ''x'' such that ''a<sup>x</sup>'' = ''b'', or failure
 
 Initialise ''i'' &larr; 0, ''a''<sub>0</sub> &larr; 0, ''b''<sub>0</sub> &larr; 0, ''x''<sub>0</sub> &larr; 1 &isin; ''G''
 
 '''loop'''
     ''i'' &larr; ''i'' + 1
 
     ''x<sub>i</sub>'' &larr; ''f''(''x''<sub>''i''−1</sub>),
     ''a<sub>i</sub>'' &larr; ''g''(''x''<sub>''i''−1</sub>, ''a''<sub>''i''−1</sub>),
     ''b<sub>i</sub>'' &larr; ''h''(''x''<sub>''i''−1</sub>, ''b''<sub>''i''−1</sub>)
 
     ''x''<sub>2''i''−1</sub> &larr; ''f''(''x''<sub>2''i''−2</sub>),
     ''a''<sub>2''i''−1</sub> &larr; ''g''(''x''<sub>2''i''−2</sub>, ''a''<sub>2''i''−2</sub>),
     ''b''<sub>2''i''−1</sub> &larr; ''h''(''x''<sub>2''i''−2</sub>, ''b''<sub>2''i''−2</sub>)
     ''x''<sub>2''i''</sub> &larr; ''f''(''x''<sub>2''i''−1</sub>),
     ''a''<sub>2''i''</sub> &larr; ''g''(''x''<sub>2''i''−1</sub>, ''a''<sub>2''i''−1</sub>),
     ''b''<sub>2''i''</sub> &larr; ''h''(''x''<sub>2''i''−1</sub>, ''b''<sub>2''i''−1</sub>)
 '''while''' ''x<sub>i</sub>'' &ne; ''x''<sub>2''i''</sub>
 
 ''r'' &larr; ''b<sub>i</sub>'' − ''b''<sub>2''i''</sub>
 '''if''' r = 0 '''return failure'''
 '''return''' ''r''<sup><span class="nowrap" style="padding-left:0.1em">−1</span></sup>(''a''<sub>2''i''</sub> − ''a<sub>i</sub>'') mod ''n''

==Example==
Consider, for example, the group generated by 2 modulo <math>N=1019</math> (the order of the group is <math>n=1018</math>, 2 generates the group of units modulo 1019). The algorithm is implemented by the following [[C++]] program:

<source lang="cpp">
#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;
}
</source>

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 <math>2^{681} 5^{378} = 1010 = 2^{301} 5^{416} \pmod{1019}</math> and so <math>(416-378)\gamma = 681-301 \pmod{1018}</math>, for which <math>\gamma_1=10</math> is a solution as expected. As <math>n=1018</math> is not [[Prime number|prime]], there is another solution <math>\gamma_2=519</math>, for which <math>2^{519} = 1014 = -5\pmod{1019}</math> holds.

==Complexity==
The running time is approximately <math>\mathcal{O}(\sqrt{n})</math>. If used together with the [[Pohlig–Hellman algorithm]], the running time of the combined algorithm is <math>\mathcal{O}(\sqrt{p})</math>, where <math>p</math> is the largest prime [[Divisor|factor]] of <math>n</math>.

==References==
{{Reflist}}
*{{cite journal |first=J. M. |last=Pollard |title=Monte Carlo methods for index computation (mod ''p'') |journal=[[Mathematics of Computation]] |volume=32 |year=1978 |issue=143 |pages=918–924 |doi= 10.2307/2006496 |jstor=2006496 }}
*{{cite book |first1=Alfred J. |last1=Menezes |first2=Paul C. |last2=van Oorschot |first3=Scott A. |last3=Vanstone |chapter-url=http://www.cacr.math.uwaterloo.ca/hac/about/chap3.pdf |title=Handbook of Applied Cryptography |chapter=Chapter 3 |year=2001 }}

{{Number-theoretic algorithms}}

[[Category:Logarithms]]
[[Category:Number theoretic algorithms]]

{{Sourceattribution|Pollard's rho algorithm for logarithms}}