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'[1], 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.

  • [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.
 
Source
< Prev   CONTENTS   Source   Next >