Problem 8.

An algorithm for extracting discrete logarithms

Let p be a large prime and g a fixed primitive root of p. Let h Z^*_p

be the modular inverse of g, so g h 1 (mod p). Let a Z^*_p . Define the following lists of elements in Z^*_{p :} y_i a hⁱ (mod p), 0 i m - 1; z_j (g^m)^j (mod p), 0 j k - 1. Here, m is a positive integer (an as yet unspecified parameter) and k is the smallest integer with k (p - 1)/m.

(b) Consider the following procedure for computing the discrete logarithm of a with respect to g. 1. Compute the list Y = (y_0, y₁ ... y_m-1 ) 2. If 1 y_i (mod p) for some i { 0, 1, ...m - 1} , then output i and quit. 3. Compute the list Z = (z_0, z_1, z₂ ,... ) until an element z_j is found that appears in Y. 4. Upon finding such a match, say z_j = y_i, output x j m + i (mod p - 1). Prove that this procedure terminates and outputs the discrete logarithm of a.

(c) Assuming the worst case scenario (i.e. the entire list Z = (z_{0 ,} z_{1 ,...}; z_k-1) needs to be generated), how many modular multiplication are required to extract the discrete logarithm of a using the procedure above? Your count should be as accurate as possible (i.e. don't count modular multiplications that aren't needed). You may assume that the quantities m, k, h and g^m (mod p) have been precomputed as they are independent of a. You may also ignore the cost of searching the list Y for an element z Z.

(d) How should m be chosen to minimize the number of modular multiplication required by the procedure above? Explain your choice.

(e) Let p = 107. i. Use the primitive root test from class to verify that 2 is a primitive root of p. Show your work.

ii. Use the procedure from part (b) and your choice of m from part (d) to compute the discrete logarithm of 6 with respect to 2 in Z^*₁₀₇ . Show your work. You may want to verify that your final answer is correct.

.

Transcribed image text