Pollard's rho algorithm for logarithms is an algorithm introduced by 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
γ
β
belongs to a cyclic group
The algorithm computes integers
If the underlying group is cyclic of order
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
is one of the solutions of the equation
{\displaystyle (B-b)\gamma =(a-A){\pmod {n}}}
Solutions to this equation are easily obtained using the extended Euclidean algorithm.
To find the needed
the algorithm uses Floyd's cycle-finding algorithm to find a cycle in the sequence
α
is assumed to be random-looking and thus is likely to enter into a loop of approximate length
One way to define such a function is to use the following rules: Partition
into three disjoint subsets
of approximately equal size using a hash function.
be a cyclic group of order
α , β ∈
be the map and define maps
by Consider, for example, the group generated by 2 modulo
(the order of the group is
, 2 generates the group of units modulo 1019).
The algorithm is implemented by the following C++ program: The results are as follows (edited): That is
is a solution as expected.
is not prime, there is another solution
The running time is approximately
If used together with the Pohlig–Hellman algorithm, the running time of the combined algorithm is
is the largest prime factor of