Pollard's kangaroo algorithm: Difference between revisions

Revision as of 19:06, 21 April 2009

Revision as of 19:10, 21 April 2009

Line 3:

==The algorithm==

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\}\subset Z_n</math>. We may search the entire range of possible logarithms by setting <math>a=0</math> and <math>b=pn-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>.

Line 24:

:A) <math>y_j = 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{pn}</math>

:and so we are done.