Thursday 29 September class

• Warmup activity: finding a pattern in the powers of 8 mod 5, and in the powers of 5 mod 3
We observed that in each case the powers cycled through all the possible nonzero residues, ending with 1:

81 ≡ 3 (mod 5)	51 ≡ 2 (mod 3)
82 ≡ 4 (mod 5)	52 ≡ 1 (mod 3)
83 ≡ 2 (mod 5)	53 ≡ 2 (mod 3)
84 ≡ 1 (mod 5)	54 ≡ 1 (mod 3)
85 ≡ 3 (mod 5)	55 ≡ 2 (mod 3)
... etc. ...	... etc. ...

Next time I will show you how you can exploit modular arithmetic to keep the numbers small when doing this type of computation - which will partially answer the question of what happens in RSA when the numbers get too big for even a computer to handle.

These are examples of Fermat's Little  Theorem:
If p is a prime number, and a is any integer which does not have p as a factor, then
a^p-1 ≡ 1 (mod p)

In the two examples we had
a=8, p=5: 8^5-1 = 8⁴ ≡ 1 (mod 5)
a=5, p=3: 5^3-1 = 5² ≡ 1 (mod 3)

This Theorem plays a role in proving that the RSA algorithm works. (see the notes)

• We showed how the two public keys and the private key are found, first by the example in my notes, and then by the example in this reading (Serge Matovic's homepage: see Section 1). We showed how his method for finding the private key is really the same as the method in my notes.:

In my notes, to find the private key d, we solve the Diophantine equation ed - my = 1 for integers d and y (actually, we want them to be natural numbers in fact)
So in Serge's example, we would be solving 7d - 20y =1 for natural numbers d and y
In Serge's webpage, he does this by solving the modular equation 7d ≡ 1 (mod 20)
By the division algorithm, this is the same as saying that 7d = 20q + 1 for some whole number q.
If you take our Diophantine equation and add 20y to both sides, you get exactly this - it doesn't matter whether you call the quotient q or y. 

So these are actually the same procedure written in different ways. It's an equally difficult or easy problem either way. It is just a matter of taste which way to go.

In a sense the RSA algorithm is a generalization of the Little Fermat Theorem, as discussed in the background article.

Homework:
• Journal assignment:

• Problems related to the RSA algorithm: (corrected problem number references)
1) Choosing the prime numbers p=3 and q=5, compute m [as in my notes on RSA] and then find possible values for e and d, using trial and error. Record your trial and error or other reasoning to explain how you got them! And try to keep them small.
2) Using the public and private keys you found in problem (1), encode the message 809.
3) Using the private key you found in problem (1), decode the encoded message from problem (4) and show that the decoded message is the original message 809.


• For future use: you will be asked to write a short essay on some aspect of the RSA algorithm. Start thinking about this and doing research on the area you would like to write about. Here are some suggestions (pick ONE, or make up one of your own):
    • The history of the RSA algorithm: how and why it came to be developed by Rivest, Shamir, and Adleman
    • How RSA is used today
    • How long would it take the fastest computer to factor large numbers? What progress has been made on this problem in recent years?

Next up: Explaining why the RSA algorithm works, and how to exploit modular arithmetic to keep the numbers for getting too large when we take those powers. This will involve using Fermat's Little Theorem: please view this video which gives an example  and then shows you how it can be used!