Reading: Read sections 7.1, 7.2, 7.3
Exercises:
Let’s work out a small example of RSA encryption. You’ll want a calculator! Feel free to use WolframAlpha, which will do the arithmetic for you. For example, if you type “536 mod 11” you’ll get the smallest remainder 8, so that \(536 \equiv 8 \mod 11\).
Let \(pq = 77\), and \(e = 13\). Pick an integer message \(0 \le x < 77\).
Compute your encrypted message, that is, the smallest positive remainder \(r\) satisfying \(x^e \equiv r \mod 77\).
Using the private key \(d = 37\), what remainder must you find to decrypt your original message? Find the remainder. Does it agree with \(x\) from part a?
What are the primes \(p\) and \(q\)?
We’ll pick \(x = 7\) for this example.
\(7^13 \equiv 35 \mod 77 \).
\(35^37 \equiv 7 \mod 77\), our original message!
We factor \(77\) (it’s only easy because it’s such a small number) to get \(p=7, q=11\).
True or False: If \(a \equiv 0 \mod b\) and \(b \equiv 0 \mod c\) then \(a \equiv 0 \mod c\).
True. The hypothesis is equivalent to saying \(b \mid a\) and \(c \mid b\), which implies that \(c \mid a\) by homework 5.3.a, which is equivalent to saying \(a \equiv 0 \mod c\).
Devise a new scenario that can be described using graphs. Be sure to explain what the vertices are, and what the edges are.
For example, vertices could be airports and there could be an edge between airports if there is a direct flight between the two of them. We could answer questions like, “What’s the smallest number of layovers you’d need to get from Denver to Nairobi?”
Draw an example of a graph or explain why one cannot exist: Is there a graph…
With 6 vertices all of which have degree 3?
With 5 vertices all of which have degree 3?
With 6 vertices of degrees 0,1,1,3,4,5?
With 7 vertices of degrees 2,2,2,2,3,3,6?
Exists.
Can’t exist; has an odd number of odd degree vertices.
Can’t exist; the vertex of degree 5 must connect to the vertex of degree 0 which is impossible.
Exists.