Exhaustive search
The most obvious algorithm for GDLP (Definition 3.52) is to successively compute a^{0}, a^{1}, a^{2},... 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 = a^{x}, then one can write x = im+j, where 0 < i.j < m. Hence, a^{x} = a^{im} a^{J}, which implies (3(a~^{m}y = a^{J}. 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 = log_{Q} (3.
- 1. Set m<— >fn].
- 2. Construct a table with entries (j, a^{J}) 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 = q^{j} 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 ZJ_{1:S}) Let p = 113. The element a = 3 is a generator of ZJ_{13} of order n = 112. Consider (3 = 57. Then log_{3} 57 is computed as follows.
- 1. Set m-<— [/Tl2] = 11.
- 2. Construct a table whose entries are (j, a^{J} 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} = 38^{11} 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 • 58^{4} mod 113 |
57 |
29 |
100 |
37 |
112 |
55 |
20 |
39 |
2 |
3 |
Finally, since 3a~^{9m} = 3 = a^{1}, (3 = a^{100} and, therefore, log_{3} 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.