13.6 Consider the problem of creating domain parameters for DSA. Suppose we have already found primes p and q such that q|(p - 1). Now we need to find g E Zp with g of order q mod p. Consider
the following two algorithms:
a. Prove that the value returned by Algorithm 1 has order q. b. Prove that the value returned by Algorithm 2 has order q. c. Suppose p = 40193 and q = 157. How many loop iterations do you expect Algorithm 1 to make before it finds a generator? d. If p is 1024 bits and q is 160 bits, would you recommend using Algorithm 1 to find g? Explain. e. Suppose p = 40193 and q = 157. What is the probability that Algorithm 2 computes a generator in its very first loop iteration? (If it is helpful, you may use the fact that
when answering this question.)