The Mathematics of Public-Key Cryptography, Assignment 3

due 11:30 AM, October 31, 2000

1. Briefly describe how to modify Shanks' algorithm to compute the logarithm of beta to the base alpha in a group G if it 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) ).
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.
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.
   1. 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.
   2. 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.
   3. Use the Pohlig-Hellman algorithm to compute the log of 3344 to the base 3 in the multiplicative group Z_{24389}*.