 Exhaustive search

The most obvious algorithm for GDLP (Definition 3.52) is to successively compute a0, a1, a2,... until (3 is obtained. This method takes O(n) multiplications, where n is the order of q, and is therefore inefficient if n is large (i.e. in cases of cryptographic interest).

Baby-step giant-step algorithm

Let m = ГУН where n is the order of a. The baby-step giant-step algorithm is a time- memory trade-off of the method of exhaustive search and is based on the following observation. If (3 = ax, then one can write x = im+j, where 0 < i.j < m. Hence, ax = aim aJ, which implies (3(a~my = aJ. This suggests the following algorithm for computing x.

3.56 Algorithm Baby-step giant-step algorithm for computing discrete logarithms

INPUT: a generator a of a cyclic group G of order n, and an element ,3 e G.

OUTPUT: the discrete logarithm r = logQ (3.

• 1. Set m<— >fn].
• 2. Construct a table with entries (j, aJ) for 0 < j < m. Sort this table by second component. (Alternatively, use conventional hashing on the second component to store the entries in a hash table; placing an entry, and searching for an entry in the table takes constant time.)
• 3. Compute a~m and set 7■*—/?.
• 4. For i from 0 to m - 1 do the following:
• 4.1 Check if 7 is the second component of some entry in the table.
• 4.2 If 7 = qj then retum(x = im + j).
• 4.3 Set 7<—7 • a-m.

Algorithm 3.56 requires storage for 0(/n) group elements. The table takes 0(/n) multiplications to construct, and 0(^/nlg n) comparisons to sort. Having constructed this table, step 4 takes 0(s/n) multiplications and 0(^/n) table look-ups. Under the assumption that a group multiplication takes more time than lg n comparisons, the running time of Algorithm 3.56 can be stated more concisely as follows.

• 3.57 Fact The running time of the baby-step giant-step algorithm (Algorithm 3.56) is 0(у/п) group multiplications.
• 3.58 Example (baby-step giant-step algorithm for logarithms in ZJ1:S) Let p = 113. The element a = 3 is a generator of ZJ13 of order n = 112. Consider (3 = 57. Then log3 57 is computed as follows.
• 1. Set m-<— [/Tl2] = 11.
• 2. Construct a table whose entries are (j, aJ mod p) for 0 < j < 11:
 j 0 1 2 3 4 5 G 7 8 9 10 3' mod 113 1 3 9 27 81 17 51 40 7 21 63

and sort the table by second component:

 j 0 1 8 2 5 9 3 7 6 10 4 У mod 113 1 3 7 9 17 21 27 40 51 63 81

3. Using Algorithm 2.142, compute a 1 = 3 1 mod 113 = 38 and then compute

a~m = 3811 mod 113 = 58.

4. Next, 7 = (3a~mi mod 113 for i = 0,1,2,... is computed until a value in the second row of the table is obtained. This yields:

 i 0 1 2 3 4 5 6 7 8 9 7 = 57 • 584 mod 113 57 29 100 37 112 55 20 39 2 3

Finally, since 3a~9m = 3 = a1, (3 = a100 and, therefore, log3 57 = 100. □

3.59 Note (restricted exponents) In order to improve performance, some cryptographic protocols which use exponentiation in Z* select exponents of a special form, e.g. having small Hamming weight. (The Hamming weight of an integer is the number of ones in its binary representation.) Suppose that p is a A--bit prime, and only exponents of Hamming weight t are used. The number of such exponents is . Algorithm 3.56 can be modified to search the exponent space in roughly (A) steps. The algorithm also applies to exponents that are restricted in certain other ways, and extends to all finite groups.