Heresy Most Foul: Applications of Number Theory

1. To encode a message, we must convert it from our standard alphabet into something we can manipulate numerically. For example, we encode the word “MATH” as 13, 01, 20, 08; each letter is replaced by its place in the alphabet.

   1. Encode GOOD and TIMES using the same rule.

   2. Decode 06, 15, 18 and 01, 12, 12.

2. Once a message is encoded, we can encipher it using the following rule: \(f(M) = M^e\) (mod \(p\)). Here, \(M\) represents the original message (or at least, one encoded character), and \(M^e\) is the enciphered character. This type of rule is called a power cipher. We have used this rule with \(e=3\) and \(p = 29\) to encipher a message; the enciphered message is 19, 4.

   1. What was the original encoded message? What was the decoded (or plaintext) message?

   2. Is there any reason \(p = 29\) was chosen instead of \(p = 26\)?

   3. Would \(e=2\) have worked? What about \(e = 4\) or \(e = 5\)? Can you find a general rule for the “good” values of \(e\), if \(p = 29\)? For any given value of \(p\), how do we know if a value of \(e\) will be “good”?