Pollard's kangaroo algorithm: Difference between revisions

Revision as of 02:38, 25 August 2007

Revision as of 04:30, 25 August 2007

Line 5:

Suppose <math>G</math> is a finite cyclic group of order <math>n</math> which is generated by the element <math>\alpha</math>, and we seek to find the discrete logarithm <math>x</math> of the element <math>\beta</math> to the base <math>\alpha</math>. In other words, we seek <math>x \in Z_n</math> such that <math>\alpha^x = \beta</math>. The lambda algorithm allows us to search for <math>x</math> in some subset <math>\{a,\ldots,b\}</math> of <math>Z_n</math>. We may search the entire range of possible logarithms by setting <math>a=0</math> and <math>b=p-1</math>, although in this case Pollard's rho algorithm is more efficient. We proceed as follows:

*1. Choose a set <math>S</math> of integers and define a [[pseudorandom]] map <math>f: G \rightarrow S</math>.

*2. Choose an integer <math>N</math> and compute a sequence of group elements <math>\{x_0,x_1,\ldots,x_N\}</math> according to:

# <math>x_0 = \alpha^b</math>

#* <math>x_0 = \alpha^b</math>
* <math>x_{i+1} = x_i\alpha^{f(x_i)}</math> for <math>i=0,1,\ldots,N-1</math>

3. Compute

*Compute <math>d = \sum_{i=0}^i={N-1}f(x_i)</math>. Observe that <math>x_N = x_0\alpha^d = \alpha^{b+d}</math>.

:<math>d = \sum_{i=0}^i={N-1}f(x_i)</math>.

* Begin computing a second sequence of group elements <math>\{y_0,y_1,\ldots\}</math> according to:

Observe that:

# <math>y_0 = \beta</math>

# :<math>y_{i+1}x_N = y_ix_0\alpha^{f(y_i)}</math>d for= <math>i=0,1,\ldots,N-1alpha^{b+d}</math>.

*4. Begin computing a second sequence of group elements <math>\{y_0,y_1,\ldots\}</math> according to:

#* <math>x_0y_0 = \alpha^bbeta</math>

* <math>y_{i+1} = y_i\alpha^{f(y_i)}</math> for <math>i=0,1,\ldots,N-1</math>

and a corresponding sequence of integers <math>\{d_0,d_1,\ldots\}</math> according to:

:<math>d_n = \sum_{i=0}^{n-1}f(y_i)</math>.

Observe that :
:<math>y_i = y_0\alpha^d_i = \beta\alpha^{d_i}</math> for <math>i=0,1,\ldots,N-1</math>

*5. Stop computing terms of <math>\{y_i\}</math> and <math>\{d_i\}</math> when either of the following conditions are met:

# <math>y_i = x_N</math> for some <math>j</math>. If the sequences <math>\{x_i\}</math> and <math>\{y_j\}</math> "collide" in this manner, then we have: <math>x_N = y_j \Rightarrow \alpha^{b+d} = \beta\alpha^{d_j} \Rightarrow \beta = \alpha^{b+d-d_j} \Rightarrow x \equiv b+d-d_j \pmod{p}</math> and so we are done.

#:A <math>d_iy_i >= b-a+dx_N</math>. for If this occurs, then the algorithm has failed to findsome <math>xj</math>. Subsequent attempts can be made by changingIf the choice ofsequences <math>S\{x_i\}</math> and/or <math>f\{y_j\}</math>. "collide" in this manner, then we have:

# <math>y_i = x_N</math> for some <math>j</math>. If the sequences <math>\{x_i\}</math> and <math>\{y_j\}</math> "collide" in this manner, then we have: :<math>x_N = y_j \Rightarrow \alpha^{b+d} = \beta\alpha^{d_j} \Rightarrow \beta = \alpha^{b+d-d_j} \Rightarrow x \equiv b+d-d_j \pmod{p}</math> and so we are done.

:and so we are done.

:B <math>d_i > b-a+d</math>. If this occurs, then the algorithm has failed to find <math>x</math>. Subsequent attempts can be made by changing the choice of <math>S</math> and/or <math>f</math>.

==Complexity==