Content deleted Content added
No edit summary |
|||
Line 1:
'''Pollard's rho algorithm for logarithms''' is an algorithm introduced by [[John Pollard]] in 1978 for solving the [[discrete logarithm]] problem analogous to [[Pollard's rho algorithm]] for solving 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 [[Group (mathematics)|group]] <math>G</math> generated by <math>\alpha</math>. The algorithm computes integers <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>. Assuming, for simplicity, that the underlying group is cyclic of order <math>n</math>, we can calculate <math>\gamma</math> as a solution of the equation <math>(B-b)\gamma = (a-A) \pmod{n}</math>.
| |||