Suppose Amelia sets up an RSA cryptosystem with a modulus n = pq, where p and q are large primes, and a pubic key k. The public key is chosen so that 2k > n. She asks Bertrand 'What day of the week will the secret meeting be held on?', and instructs him to reply using the cryptosystem by encoding 'Monday' as the message '2', 'Tuesday' as 3, ..., Sunday' as '8', then encrypting the message using the public key k. You have intercepted Bertrand's encrypted message M̅.

(a) Explain how you can easily determine the day of the secret meeting from M̅ without factoring the modulus n. That the we started the numbering at 2 since 0 and 1 always encrypt as 0 and 1.

(b) Now suppose that the actual modulus is n = 1073 and the public key is k = 17. You have intercepted Bertrand's encrpyted message M̅ = 709. Use your method from (a) to find the day of the secret meeting, without factoring 1073. (Of course, it is easy to factor 1073, but we are keeping the numbers small so that your computations are easy to do.)