(programming required) Key generation. Given two prime numbers p and q as input, produce a public and private RSA keypair he, ni and hd, ni. (Hint: Exercises 7.31 and 7.103 will be helpful. To pick e,...

(programming required) Key generation. Given two prime numbers p and q as input, produce a public and private RSA keypair he, ni and hd, ni. (Hint: Exercises 7.31 and 7.103 will be helpful. To pick e, you may wish to simply try all odd numbers and use Exercise 7.31—you could make this step faster, but generally speaking this slightly slower approach will still be fast enough.)

Exercise 7.31

Explain precisely how to use binary search to find the eth root of me efficiently. Then explain precisely why this binary-search approach doesn’t work to find the eth root of me mod n in general.