Pollard's rho algorithm for logarithms: Difference between revisions

Revision as of 06:37, 11 February 2016

Revision as of 06:40, 11 February 2016

Line 6:

==Algorithm==

Let <math>{{mvar|G</math>}} be a cyclic group of order <math>{{mvar|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 a map

:<math>

f(x) = \left\{\begin{matrixcases}

\beta x & x\in S_0\\

x^2 & x\in S_1\\

\alpha x & x\in S_2

\end{matrixcases}\right.

</math>

Line 19:

:<math>\begin{align}

g(x,n) &= \left\{\begin{matrixcases}

n & x\in S_0\\

2n \ (\bmod \ p) & x\in S_1\\

n+1 \ (\bmod \ p) & x\in S_2

\end{matrixcases}\right.

\\

h(x,n) &= \left\{\begin{matrixcases}

n+1 \ (\bmod \ p) & x\in S_0\\

2n \ (\bmod \ p) & x\in S_1\\

n & x\in S_2

\end{matrixcases}\right.

\end{align}</math>

Line 53:

'''return''' ''x''

'''else''' <u># ''x_i'' &ne; ''x''_2''i''</u>

''i'' &larr; ''i+1''+1,

'''break loop'''

'''end if'''