Pollard's rho algorithm for logarithms: Difference between revisions

Revision as of 19:07, 15 October 2015

Revision as of 04:28, 31 October 2015

Line 1:

'''Pollard's rho algorithm for logarithms''' is an algorithm introduced by [[John Pollard (mathematician)|John Pollard]] in 1978 forto solvingsolve the [[discrete logarithm]] problem, analogous to [[Pollard's rho algorithm]] forto solvingsolve the [[Integerinteger 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 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>.

Line 52:

==Example==

Consider, for example, the group generated by 2 modulo <math>N=1019</math> (the order of the group is <math>n=1018</math>, 2 generates the group of units modulo 1019). The algorithm is implemented by the following [[C++]] program:

generates the group of units modulo 1019). The algorithm is implemented by the following [[C++_(programming_language)|C++]] program:

<source lang="cpp">