20 points

Let n=1111, and e be an odd prime of your own choice less than n. Let m = 30a+b, where a and b are the encodings of your first and last initials with A encoded as 1, B as 2, ..., Z as 26.
1. If e and n are interpreted as a public key, find the private key that will decrypt a message encoded with this public key.
2. Check your answer by using the public key to encrypt m and your private key to decrypt the result. In each case, show the intermediate steps of the exponentiation algorithm that you use.
Consider each of the integers 10111, 11111, 11101, and 12329 as candidate primes. Apply the probabilistic primality testing algorithm (the simple form, that ignores Carmichael numbers) to each one by choosing 5 witness that sum to the candidate prime. If it turns out that you don't need 5 witnesses, you may choose fewer. What can you conclude about the primality of each of the integers after your tests?