Pollard's rho algorithm for logarithms: Difference between revisions

Revision as of 18:59, 20 June 2022

Revision as of 11:10, 30 June 2022

Line 8:

==Algorithm==

Let <math>G</math> be a [[cyclic group]] of order <math>pn</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>

Line 21:

:<math>\begin{align}

g(x,nk) &= \begin{cases}

nk & x\in S_0\\

2n2k \pmod {p-1n} & x\in S_1\\

nk+1 \pmod {p-1n} & x\in S_2

\end{cases}

\\

h(x,nk) &= \begin{cases}

nk+1 \pmod {p-1n} & x\in S_0\\

2n2k \pmod {p-1n} & x\in S_1\\

nk & x\in S_2

\end{cases}

\end{align}</math>

Line 53:

''r'' &larr; ''b_i'' - ''b''_2''i''

'''if''' r = 0 '''return failure'''

''x'' &larr; ''r''⁻¹(''a''_2''i'' - ''a_i'') mod ''p-1n''

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

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