Practice Quiz 3, M203E

Instructions: The quiz is open book (any books) and open notes (any notes or written material).

[1] (a) What is the remainder if you divide 34657863295 by 9? Show your work or explain how you get your answer.

(b) What is the remainder if you divide 3213418 by 5? Show your work or explain how you get your answer.

[2] Decipher the following message, given that it was encrypted using a Caesar cipher (i.e., the letters of the alphabet are just shifted): ju xbt uif cftu pg ujnft, ju xbt uif xpstu pg ujnft.

[3] Note that 97 is a prime number.

(a) Find the remainder when you divide 385 = 5*77 by 96.

(b) Compute 45^{385} mod 97. Explain how you obtain your answer.

[4] In the cipher using the formula y = x^{5} mod 17, the encryption exponent is e = 5.
Find the decryption exponent d (thus the decryption formula is x = y^{d} mod 17.)
Explain how you get your answer.

[5] In the RSA cipher using the formula y = x^{3} mod 33, the encryption exponent is e = 3.
Find the decryption exponent d (thus the decryption formula is x = y^{d} mod 33.)
Explain how you get your answer.

[6] For the encryption formula y = x^{e} mod p where p is a prime, give an example of
an appropriate prime p and an appropriate encryption exponent e > 1, if the numbers associated to plaintext
characters could be as big as 50.

[7] For the encryption formula y = x^{e} mod pq where p and q are different primes, give an example of
appropriate primes p and q and an appropriate encryption exponent e > 1, if the numbers associated to plaintext
characters could be as big as 50.