Pollard's rho algorithm for logarithms

Pollard's rho algorithm for logarithms is an algorithm introduced by <a href="/facts/John_Pollard_(mathematician)/wI1GHPYh">John Pollard</a> in 1978 to solve the <a href="/facts/Discrete_logarithm/k8TXh5bL">discrete logarithm</a> problem, analogous to <a href="/facts/Pollard%27s_rho_algorithm/7TjSCKK5">Pollard's rho algorithm</a> to solve the <a href="/facts/Integer_factorization/EjMCTz2t">integer factorization</a> problem.
The goal is to compute 
 
 
 
 γ
 
 
 {\displaystyle \gamma }
 
 such that 
 
 
 
 
 α
 
 γ
 
 
 =
 β
 
 
 {\displaystyle \alpha ^{\gamma }=\beta }
 
, where 
 
 
 
 β
 
 
 {\displaystyle \beta }
 
 belongs to a <a href="/facts/Cyclic_group/JL5zfFuL">cyclic group</a> 
 
 
 
 G
 
 
 {\displaystyle G}
 
 generated by 
 
 
 
 α
 
 
 {\displaystyle \alpha }
 
. The algorithm computes <a href="/facts/Integer/PUwwrawx">integers</a> 
 
 
 
 a
 
 
 {\displaystyle a}
 
, 
 
 
 
 b
 
 
 {\displaystyle b}
 
, 
 
 
 
 A
 
 
 {\displaystyle A}
 
, and 
 
 
 
 B
 
 
 {\displaystyle B}
 
 such that 
 
 
 
 
 α
 
 a
 
 
 
 β
 
 b
 
 
 =
 
 α
 
 A
 
 
 
 β
 
 B
 
 
 
 
 {\displaystyle \alpha ^{a}\beta ^{b}=\alpha ^{A}\beta ^{B}}
 
. If the underlying <a href="/facts/Group_(mathematics)/IQTYqINt">group</a> is cyclic of <a href="/facts/Order_of_a_group/Cl3tKGFg">order</a> 
 
 
 
 n
 
 
 {\displaystyle n}
 
, by substituting 
 
 
 
 β
 
 
 {\displaystyle \beta }
 
 as 
 
 
 
 
 
 α
 
 
 γ
 
 
 
 
 {\displaystyle {\alpha }^{\gamma }}
 
 and noting that two powers are equal <a href="/facts/If_and_only_if/bYSxGJ66">if and only if</a> the exponents are equivalent modulo the order of the base, in this case modulo 
 
 
 
 n
 
 
 {\displaystyle n}
 
, we get that 
 
 
 
 γ
 
 
 {\displaystyle \gamma }
 
 is one of the solutions of the equation 
 
 
 
 (
 B
 −
 b
 )
 γ
 =
 (
 a
 −
 A
 )
 
 
 (
 mod
 
 n
 )
 
 
 
 {\displaystyle (B-b)\gamma =(a-A){\pmod {n}}}
 
. Solutions to this equation are easily obtained using the <a href="/facts/Extended_Euclidean_algorithm/wmomforl">extended Euclidean algorithm</a>.
To find the needed 
 
 
 
 a
 
 
 {\displaystyle a}
 
, 
 
 
 
 b
 
 
 {\displaystyle b}
 
, 
 
 
 
 A
 
 
 {\displaystyle A}
 
, and 
 
 
 
 B
 
 
 {\displaystyle B}
 
 the algorithm uses <a href="/facts/Floyd%27s_cycle-finding_algorithm/S1dA6pJr">Floyd's cycle-finding algorithm</a> to find a cycle in the sequence 
 
 
 
 
 x
 
 i
 
 
 =
 
 α
 
 
 a
 
 i
 
 
 
 
 
 β
 
 
 b
 
 i
 
 
 
 
 
 
 {\displaystyle x_{i}=\alpha ^{a_{i}}\beta ^{b_{i}}}
 
, where the <a href="/facts/Function_(mathematics)/CdReEKCh">function</a> 
 
 
 
 f
 :
 
 x
 
 i
 
 
 ↦
 
 x
 
 i
 +
 1
 
 
 
 
 {\displaystyle f:x_{i}\mapsto x_{i+1}}
 
 is assumed to be random-looking and thus is likely to enter into a loop of approximate length 
 
 
 
 
 
 
 
 π
 n
 
 8
 
 
 
 
 
 {\displaystyle {\sqrt {\frac {\pi n}{8}}}}
 
 after 
 
 
 
 
 
 
 
 π
 n
 
 8
 
 
 
 
 
 {\displaystyle {\sqrt {\frac {\pi n}{8}}}}
 
 steps. One way to define such a function is to use the following rules: <a href="/facts/Partition_of_a_set/VeP9g8CA">Partition</a> 
 
 
 
 G
 
 
 {\displaystyle G}
 
 into three <a href="/facts/Disjoint_subset/nLr8XRVd">disjoint subsets</a> 
 
 
 
 
 S
 
 0
 
 
 
 
 {\displaystyle S_{0}}
 
, 
 
 
 
 
 S
 
 1
 
 
 
 
 {\displaystyle S_{1}}
 
, and 
 
 
 
 
 S
 
 2
 
 
 
 
 {\displaystyle S_{2}}
 
 of approximately equal size using a <a href="/facts/Hash_function/rk6MlCt3">hash function</a>. If 
 
 
 
 
 x
 
 i
 
 
 
 
 {\displaystyle x_{i}}
 
 is in 
 
 
 
 
 S
 
 0
 
 
 
 
 {\displaystyle S_{0}}
 
 then double both 
 
 
 
 a
 
 
 {\displaystyle a}
 
 and 
 
 
 
 b
 
 
 {\displaystyle b}
 
; if 
 
 
 
 
 x
 
 i
 
 
 ∈
 
 S
 
 1
 
 
 
 
 {\displaystyle x_{i}\in S_{1}}
 
 then increment 
 
 
 
 a
 
 
 {\displaystyle a}
 
, if 
 
 
 
 
 x
 
 i
 
 
 ∈
 
 S
 
 2
 
 
 
 
 {\displaystyle x_{i}\in S_{2}}
 
 then increment 
 
 
 
 b
 
 
 {\displaystyle b}
 
.

Pollard's rho algorithm for logarithms open-in-new

Pollard's rho algorithm for logarithms