(For some of these problems, you’ll simply be able to cite a previously developed algorithm in a few words; in others, you’ll need to combine more than one algorithm or use an algorithm in a nontrivial way.)
1.Find a large prime number: say, find the smallest prime number greater than a given number x.
2.Given primes p and q, find a number e 6= 1 such that e and (p − 1)(q − 1) are relatively prime.
3.Given primes p, q and e relatively prime to (p − 1)(q − 1), compute e −1 modulo (p − 1)(q − 1).
4.Given n, e, and m ∈ Zn, compute me mod n. (Similarly, given n, d, and c, compute c d mod n.)
5.Prove that, in the RSA key-generation protocol, the number e that we choose is always odd.
6.Prove that, in the RSA key-generation protocol, the number d that we choose is also always odd.