Pollard's rho algorithm for logarithms: Difference between revisions

Revision as of 18:01, 29 August 2019

Revision as of 17:50, 1 September 2019

Line 7:

==Algorithm==

Let <math>G</math> be a [[cyclic group]] of order <math>p</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 mapmapand define maps <math>g:G\times\mathbb{Z}\to\mathbb{Z}</math> and <math>h:G\times\mathbb{Z}\to\mathbb{Z}</math> by

==Algorithm Pollard Rho kangaroo==

Pollard kangaroo solved <ref>https://gitlab.com/bitfranke/pollard-rho-kangaroo</ref>

:<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}