 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, S2> 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 x0, 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 b0, bi, b2, ■ . ■ satisfymg Xi = aa,(3b for i > 0: do = 0, b0 = 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 хг = x2». Hence aa*/3bi = aa2i(3b', and so fib'~b2i = aa2i~ai. Taking logarithms to the base a of both sides of this last equation yields Provided b, ф b2i (mod n) (note: Ьг = b2, occurs with negligible probabihty), tliis equation can then be efficiently solved to determine logQ (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 (3G. OUTPUT: the discrete logarithm x = logQ (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, , b2, using equations (3.2), (3.3), and (3.4).
• 2.2 If Xi = X2i, then do the following:

Set r<—bi — b2i 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 Z383 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 S2 if x = 0 (mod 3), and x e 53 if x = 2 (mod 3). Table 3.2 shows the values of xt, a,, bt, xu, U2i. and 1)2, at the end of each iteration of step 2 of Algorithm 3.60. Note that si4 = Х28 = 144. Finally, compute r = b 14 — 62s mod 191 = 125, r-1 = 125-1 mod 191 = 136, andr_1(a28 — ai4) mod 191 = 110. Hence, log2 228 = 110. □

 г Xi a, bi X2 i «2» b2i 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.

•  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.