Pollard’s rho algorithm for logarithms
Pollard’s rho algorithm (Algorithm 3.60) for computing discrete logarithms is a randomized algorithm with the same expected running time as the baby-step giant-step algorithm (Algorithm 3.56), but which requires a negligible amount of storage. For this reason, it is far preferable to Algorithm 3.56 for problems of practical interest. For simplicity, it is assumed in this subsection that G is a cyclic group whose order n is prune.
The group G is partitioned into three sets S'i, S_{2}> and S3 of roughly equal size based on some easily testable property. Some care must be exercised in selecting the partition; for example, 1 ф S2. Define a sequence of group elements x_{0}, xi, X2,. ■ . by xo = 1 and
for i > 0. This sequence of group elements in him defines two sequences of integers
ao, ai, d2,... and b_{0}, bi, b_{2}, ■ . ■ satisfymg Xi = a^{a,}(3^{b}‘ for i > 0: do = 0, b_{0} = 0, and for
i > 0,
and
Floyd’s cycle-finding algorithm (Note 3.8) can then be utilized to find two group elements
Xi and X2i such that х_{г} = x_{2}». Hence a^{a}*/3^{bi} = a^{a2i}(3^{b}'^{[1]}, and so fi^{b}'~^{b2i} = a^{a2i}~^{ai}. Taking logarithms to the base a of both sides of this last equation yields
Provided b, ф b_{2}i (mod n) (note: Ь_{г} = b_{2}, occurs with negligible probabihty), tliis equation can then be efficiently solved to determine log_{Q} (3.
3.60 Algorithm Pollard’s rho algorithm for computing discrete logarithms
INPUT: a generator a of a cyclic group G of prime order n, and an element (3 € G. OUTPUT: the discrete logarithm x = log_{Q} (3.
- 1. Set xo't—1, do-*—0, boi—0.
- 2. For г = 1,2,... do the following:
- 2.1 Using the quantities bf_i, andx2i_2,0,21-2, &2«-2 computed previously, compute x;, a-i, 6, andx2i, (щ, b_{2}, using equations (3.2), (3.3), and (3.4).
- 2.2 If Xi = X2i, then do the following:
Set r<—bi — b_{2}i mod n.
If r = 0 then terminate the algorithm with failure; otherwise, compute x = r^{_1} (d2i — dj) mod n and return(x).
3.61 Example (Pollard’s rho algorithm for logarithms in a subgroup of Щ_{83}) The element a = 2 is a generator of the subgroup G of Z_{383} of order n = 191. Suppose /3 = 228. Partition the elements of G into three subsets according to the rule x e S'i if ж = 1 (mod 3), x e S_{2 }if x = 0 (mod 3), and x e 5_{3} if x = 2 (mod 3). Table 3.2 shows the values of x_{t}, a,, b_{t}, xu, U2i. and 1)2, at the end of each iteration of step 2 of Algorithm 3.60. Note that si_{4} = Х28 = 144. Finally, compute r = b 14 — 62s mod 191 = 125, r^{-1} = 125^{-1} mod 191 = 136, andr^{_1}(a28 — ai_{4}) mod 191 = 110. Hence, log_{2} 228 = 110. □
г |
Xi |
a, |
bi |
X2 i |
«2» |
b_{2i} |
i |
228 |
0 |
1 |
279 |
0 |
2 |
2 |
279 |
0 |
2 |
184 |
1 |
4 |
3 |
92 |
0 |
4 |
14 |
1 |
6 |
4 |
184 |
1 |
4 |
256 |
2 |
7 |
5 |
205 |
1 |
5 |
304 |
3 |
8 |
6 |
14 |
1 |
6 |
121 |
6 |
18 |
7 |
28 |
2 |
6 |
144 |
12 |
38 |
8 |
256 |
2 |
7 |
235 |
48 |
152 |
9 |
152 |
2 |
8 |
72 |
48 |
154 |
10 |
304 |
3 |
8 |
14 |
96 |
118 |
11 |
372 |
3 |
9 |
256 |
97 |
119 |
12 |
121 |
6 |
18 |
304 |
98 |
120 |
13 |
12 |
6 |
19 |
121 |
5 |
51 |
14 |
144 |
12 |
38 |
144 |
10 |
104 |
Table 3.2: Intermediate steps of Pollard’s rho algorithm in Example 3.61.
3.62 Fact Let G be a group of order n, a prime. Assume that the function / : G —> G defined by equation (3.2) behaves like a random function. Then the expected running time of Pollard’s rho algorithm for discrete logarithms in G is ()(y/n) group operations. Moreover, the algorithm requires negligible storage.
- [1] In the rare case that Algorithm 3.60 terminates with failure, the procedure can be repeated by selecting random integers a0, b0 in the interval [1, n — 1], and starting with x0 =aa<’0b". Example 3.61 with artificially small parameters illustrates Pollard’s rho algorithm.