Pollard's rho algorithm for logarithms: Difference between revisions

Revision as of 18:59, 20 June 2022

Latest revision as of 18:02, 2 August 2024

(6 intermediate revisions by 4 users not shown)

Line 2:

'''Pollard's rho algorithm for logarithms''' is an algorithm introduced by [[John Pollard (mathematician)|John Pollard]] in 1978 to solve the [[discrete logarithm]] problem, analogous to [[Pollard's rho algorithm]] to solve the [[integer factorization]] problem.

The goal is to compute <math>\gamma</math> such that <math>\alpha ^ \gamma = \beta</math>, where <math>\beta</math> belongs to a [[cyclic group]] <math>G</math> generated by <math>\alpha</math>. The algorithm computes [[integer]]s <math>a</math>, <math>b</math>, <math>A</math>, and <math>B</math> such that <math>\alpha^a \beta^b = \alpha^A \beta^B</math>. If the underlying [[group (mathematics)|group]] is cyclic of [[order of a group|order]] <math>n</math>, by substituting <math> \beta </math> as <math> a{\alpha}^{\gamma} </math> and noting that two powers are equal [[if and only if]] the exponents are equivalent modulo the order of the base, in this case modulo <math>n</math>, we get that <math>\gamma</math> is one of the solutions of the equation <math>(B-b) \gamma = (a-A) \pmod n</math>. Solutions to this equation are easily obtained using the [[extended Euclidean algorithm]].

To find the needed <math>a</math>, <math>b</math>, <math>A</math>, and <math>B</math> the algorithm uses [[Floyd's cycle-finding algorithm]] to find a cycle in the sequence <math>x_i = \alpha^{a_i} \beta^{b_i}</math>, where the [[function (mathematics)|function]] <math>f: x_i \mapsto x_{i+1}</math> is assumed to be random-looking and thus is likely to enter into a loop of approximate length <math>\sqrt{\frac{\pi n}{8}}</math> after <math>\sqrt{\frac{\pi n}{8}}</math> steps. One way to define such a function is to use the following rules: Divide[[Partition of a set|Partition]] <math>G</math> into three [[disjoint subsetssubset]] of approximately equal size:s <math>S_0</math>, <math>S_1</math>, and <math>S_2</math> of approximately equal size using a [[hash function]]. If <math>x_i</math> is in <math>S_0</math> then double both <math>a</math> and <math>b</math>; if <math>x_i \in S_1</math> then increment <math>a</math>, if <math>x_i \in S_2</math> then increment <math>b</math>.

==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 38:

'''output:''' An integer ''x'' such that ''a^x'' = ''b'', or failure

Initialise ''i'' &larr; 0, ''a''₀ &larr; 0, ''b''₀ &larr; 0, ''x''₀ &larr; 1 &isin; ''G''

''i'' &larr; 1

'''loop'''

''x_i'' &larr; ''f''(''x''_{''i''- + 1}),

''a_i'' &larr; ''g''(''x''_''i''-1, ''a''_''i''-1),

''b_i'' &larr; ''h''(''x''_''i''-1, ''b''_''i''-1)

''x''_2''i'''' &larr; ''f''(''f''(''x''_2''i''-2−1)),

''a''_2''i'''' &larr; ''g''(''f''(''x''_2''i''-2), ''g''(''x''_2''i''-2−1, ''a''_2''i''-2−1)),

''b''_2''i'''' &larr; ''h''(''f''(''x''_2''i''-2), ''h''(''x''_2''i''-2−1, ''b''_2''i''-2−1))

''x'if'<sub>2'' i''x_i−1'' =&larr; ''f''(''x''_2''i''−2 '''then'''),

''ra''_2''i''−1 &larr; ''bg''(''x''_2''i''−2'' -, ''ba''_2''i''−2),

''b''_2''i''−1'' &larr; ''h''(''x''_2''i''-1−2, ''b''_2''i''-1−2)

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

''x''_2''i'' &larr; ''rf''⁻¹(''ax''_2''i''−1 - ''a_i'') mod ''p-1'',

''a''_2''i'''' &larr; ''g''(''x''_2''i''-1−1, ''a''_2''i''-1−1),

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

''b'else'_{2'' <i>// ''x_i'' &nelarr; ''h''(''x''_2''i''−1, ''b''}2''i''−1</sub>)

'''while''' ''x_i'' &larrne; ''x''_{2''i'' + 1}

'''end if'''

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

'''end loop'''

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

'''return''' ''r''^{<span class="nowrap" style="padding-left:0.1em">−1</span>}(''a''_2''i'' − ''a_i'') mod ''n''

==Example==

Line 117 ⟶ 116:

==References==

{{Reflist}}

*{{cite journal |first=J. M. |last=Pollard |title=Monte Carlo methods for index computation (mod ''p'') |journal=[[Mathematics of Computation]] |volume=32 |year=1978 |issue=143 |pages=918–924 |doi= 10.2307/2006496 |jstor=2006496 }}

*{{cite book |firstfirst1=Alfred J. |lastlast1=Menezes |first2=Paul C. |last2=van Oorschot |first3=Scott A. |last3=Vanstone |chapter-url=httphttps://www.cacr.math.uwaterloo.ca/hac/about/chap3.pdf |title=Handbook of Applied Cryptography |chapter=Chapter 3 |year=2001 }}

{{Number-theoretic algorithms}}