13.13 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 findg Zp with g of order q mod p. Consider the following two algorithms:
a. Prove that the value returned by Algorithm 1 has orderq .
b. Prove that the value returned by Algorithm 1 has orderq .
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 findg ? 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
its very first loop iteration? (if it is helpful, you may use the fact that when answering this question).