Assignment 3 Solutions 1. Briefly describe how to modify Shanks' algorithm to compute the logarithm of beta to the base alpha in a group G if it is specified ahead of time that this logarithm lies in the interval [s,t], where s and t are integers such that 0 <= s < t < order(alpha). Prove that the algorithm is correct, and show that its complexity is O( sqrt(t-s) ). The algorithm is as follows: (1) Let m be the ceiling of sqrt(t-s+1). Compute alpha^{mj}, 0 <= j <= m-1. (2) Sort the m ordered pairs (j, alpha^{mj}) with respect to their second coordinates, obtaining a list L_1. (3) Compute beta * alpha^{-i-s}, 0 <= i <= m-1 (4) Sort the m ordered pairs (i, beta * alpha^{-i-s}) with respect to their second coordinates, obtaining a list L_2. (5) Find a pair (j,y) in L_1 and a pair (i,y) in L_2 (i.e., a pair having identical second coordinates). (6) log _{alpha} beta = mj+i+s mod |G|. 2. The integer p=458009 is prime. alpha = 2 has order 57251 in Z_p*. Use the Pollard rho algorithm to compute the discrete logarithm in Z_p* of beta = 56851 to the base alpha. Take the initial value x_0 = 1, and define the partition (S_1,S_2,S_3) as follows: x in S_1 if x = 1 mod 3, x in S_2 if x = 0 mod 3, and x in S_3 if x = 2 mod 3. Find the smallest integer i such that x_i = x_{2i} and then compute the discrete logarithm. x_{444} = 339768, a_{444} = 22811, b_{444} = 35067 x_{888} = 339768, a_{888} = 37251, b_{888} = 5360 log_alpha beta = 40007 3. Suppose that p is an odd prime and k is a positive integer. The multiplicative group Z_{p^k}* has order p^{k-1}(p-1), and is known to be cyclic. A generator for this group is called a primitive element modulo p^k. (a) Suppose that alpha is a primitive element modulo p. Prove that at least one of alpha or alpha + p is a primitive element modulo p^2. Suppose that alpha has order p-1 in (Z_p)*. Let n denote the order of alpha in (Z_{p^2})*. alpha^n = 1 mod p^2 implies alpha^n = 1 mod p, so n = 0 mod p. Also, n divides |(Z_{p^2})*| = p^2-p. Therefore n = p-1 or n = p^2 - p. If n = p^2-p, then we're done, so assume n=p-1. Now consider alpha+p. By the same argument, alpha has order p-1 or p^2-p in (Z_{p^2})*. We show that alpha+p cannot have order p-1, which finishes the proof. We expand (alpha+p)^{p-1} using the binomial theorem: (alpha+p)^{p-1} = alpha^{p-1} + (p-1)alpha^{p-2}*p + terms divisible by p^2. Reducing modulo p^2, we see that (alpha+p)^{p-1} = alpha^{p-1} - p*alpha^{p-2} mod p^2 = 1 - p*alpha^{p-2} mod p^2. Therefore (alpha+p)^{p-1} = 1 mod p^2 if and only if alpha^{p-2} = 0 mod p. However, gcd(alpha,p)=1. Therefore, alpha+p does not have order p-1, and we're done. (b) Prove that 3 is a primitive root modulo 29 and modulo 29^2. Note: It can be shown that if alpha is a primitive root modulo p and modulo p^2, then it is a primitive root modulo p^k for all positive integers k (you do not have to prove this fact). Therefore, it follows that 3 is a primitive root modulo 29^k for all positive integers k. 28 = 2^2 * 7. To show that 3 is primitive mod 29, it suffices to show that 3^{28/2} and 3^{28/7} are not congruent to 1 mod 29. Since 3^14 = 28 mod 29 and 3^4 = 23 mod 29, we conclude that 3 is primitive mod 29. As shown in (a), the order of 3 in (Z_{29^2})* is either 28 or 28*29. To show that 3 is a primitive element, it suffices to show that 3^{28} is not congruent to 1 mod 29^2. Since 3^{28} mod (29^2) = 436, we're done. (c) Use the Pohlig-Hellman algorithm to compute the log of 3344 to the base 3 in the multiplicative group Z_{24389}*. |Z_{24389}*| = 29^2 * 28 = 29^2 * 2^2 * 7. Let a = the desired logarithm. We need to compute "a mod 29^2", "a mod 2^2" and "a mod 7". We obtain: a = 260 mod 29^2 a = 2 mod 2^2 a = 2 mod 7 Applying the Chinese remainder theorem, a = 18762 mod (29^2*28)