Content deleted Content added
→Example: n is not prime, corrected |
No edit summary |
||
Line 1:
'''Pollard's rho algorithm for logarithms''' is an algorithm for solving the [[discrete logarithm]] problem analogous to [[Pollard's rho algorithm]] for solving the [[Integer factorization]] problem.
The algorithm computes <math>\gamma</math> such that <math>\alpha ^ \gamma = \beta</math>, where <math>\beta</math> belongs to the [[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>
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 <math>f: x_i \mapsto x_{i+1}</math> is assumed to be random-looking and thus is likely to enter into a loop after approximately <math>\sqrt{\frac{\pi n}{2}}</math> steps. One way to define such a function is to use the following rules: Divide <math>G</math> into three subsets (not necessarily [[subgroup]]s) of approximately equal size: <math>G_0</math>, <math>G_1</math>, and <math>G_2</math>. If <math>x_i</math> is in <math>G_0</math> then double both <math>a</math> and <math>b</math>; if <math>x_i \in G_1</math> then increment <math>a</math>, if <math>x_i \in G_2</math> then increment <math>b</math>.
Line 96:
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>(614-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,
==References==
| |||