Due. Monday, April 18, at the beginning of class.
Write clearly readable and well thought out answers to all of the following questions.
Does 4 have an inverse mod 9? That is, does there exist an integer x such that 4x = 1 (mod 9)? If so, what is x? If not, why not?
Does 6 have an inverse mod 9? That is, does there exist an integer x such that 6x = 1 (mod 9)? If so, what is x? If not, why not?
What is the discrete square root problem? Describe the input and the output. Give an example.
Computing discrete square roots mod n, where n is the product of two primes, is, in some sense, as hard as factoring n. What mechanism is used to show that? In what sense is computing discrete square roots as hard as factoring?
If primes p = 5 and q = 11 are chosen, what are the private and public keys selected for the RSA system? What are the encoding and decoding functions?
In public key cryptography, we give away enough information to break the encryption. What makes us think that nobody can make effective use of that information?
What is a pseudo-random number generator?
Explain how design of a pseudo-random number generator can benefit from the presumed difficulty of solving some computational problems.