Pollard's rho algorithm for logarithms: Difference between revisions

Revision as of 09:26, 27 February 2022

Revision as of 18:22, 9 March 2022

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 integers[[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^{\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 [[Extendedextended 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 <math>G</math> into three [[disjoint subsets]] of approximately equal size: <math>S_0</math>, <math>S_1</math>, and <math>S_2</math>. 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==

Line 110:

51 1010 681 378 1010 301 416

That is <math>2^{681} 5^{378} = 1010 = 2^{301} 5^{416} \pmod{1019}</math> and so <math>(416-378)\gamma = 681-301 \pmod{1018}</math>, for which <math>\gamma_1=10</math> is a solution as expected. As <math>n=1018</math> is not [[prime number|prime]], there is another solution <math>\gamma_2=519</math>, for which <math>2^{519} = 1014 = -5\pmod{1019}</math> holds.

==Complexity==

The running time is approximately <math>\mathcal{O}(\sqrt{n})</math>. If used together with the [[Pohlig–Hellman algorithm]], the running time of the combined algorithm is <math>\mathcal{O}(\sqrt{p})</math>, where <math>p</math> is the largest prime [[divisor|factor]] of <math>n</math>.

==References==