Notice the generality we can get with some of the things we are now discussing. For instance, you could solve for which positive integers $a$ the congruence $ax^4\equiv 2$ mod (13) is solvable, not just for one $a$. Similarly on the theory side, what did you conjecture for the product of all primitive roots modulo $p$?
Click to the left again to hide and once more to show the dynamic interactive window 
This is something you can prove using the pieces of information from before about primitive roots fairly easily. See the homework.
Today we will introduce cryptography, and over the next few days we will see the prototype for a cool mathematical encryption system and other similar topics. During the last two days of the quad we will discuss practical issues in implementing these  namely, finding HUGE primes and factoring HUGE composite numbers. Where by huge, I mean something substantially bigger than this:
161739973449643440459282364219 369284476538761170583831963880403569823536266419618578320385122441043760\ 475692471946128923 161739973449643440459282364219 369284476538761170583831963880403569823536266419618578320385122441043760475692471946128923 
Those are peanuts by today's standards.
Cryptography is not just the science of making (and breaking) codes, as a dictionary might have it. It is the mathematical analysis of the tools of secrecy, from both the perspective of someone keeping a secret and that of the person trying to figure it out. Sometimes it is also called cryptology, while sometimes that term is reserved for a wider meaning.
There are two kinds of codes.
Mathematicians use the word code to indicate information is being stored, reserving the term cipher to talk about a way to protect that information. So, what we do when learning about this is a some of each, though mostly about ciphers.
There are many ways to encode a message; the easiest one for us will be to simply represent each letter of the English alphabet by an integer from 1 to 26. It is also easy to represent both upper and lowercase letters from 1 to 52.
We'll use the following cell to turn messages into numbers and vice versa. You encode a plaintext message (no spaces, in quotes, for our examples) and decode a positive integer.

17 17 
'Q' 'Q' 
This should be straightforward. Notice that I didn't bother separating lower and uppercase letters. In fact, no matter how complicated you get, with just a onetoone correspondence, there are only a few possibilities for each letter, and if you know the language you can just start guessing which encrypted number stands for its most common letter.
So in practice we do a few other things. For instance, one thing that is commonly done is to make longer blocks of letters, and then turn those into numbers. Presumably there are a lot more threeletter (or longer) possible blocks of letters in English to be able to decrypt things too easily. Compare the following two encodings of 'The best day of the year' and see which one might be easier to figure out.
[20, 8, 5, 2, 5, 19, 20, 4, 1, 25, 15, 6, 20, 8, 9, 19, 25, 5, 1, 18] [20, 8, 5, 2, 5, 19, 20, 4, 1, 25, 15, 6, 20, 8, 9, 19, 25, 5, 1, 18] 
For pairs, we represent the first letter as a number from 1 to 26, and the second letter as 26 times the letter number (think of it as base 26). Remember that A=1, B=2, etc.
55 'CB' 55 'CB' 
[228, 57, 499, 124, 651, 171, 228, 503, 155, 469] [228, 57, 499, 124, 651, 171, 228, 503, 155, 469] 
Whereas there are many 5s in the first one, which you could guess were Es, the second one has only one repeat (though knowing English, one might guess it was 'Th'). Notice we haven't really encrypted yet, just encoded.
With three letter blocks, there are then already $26^3=17576$ possibilities.
1404 'ZAB' 1404 'ZAB' 
So, INT HEB EGI NNI GWA STH EWO RDX could be encoded, with an extra X to fill out the space (this is, of course, also done in the middle to confuse things). We will, however, usually keep our whole message together as one item, since we want to understand the mathematical aspects most.
We will spend most of our time talking about enciphering, or encrypting, messages. This is the difficult part, after all, the details of which we want to keep secret. What is cool about modern ciphers is that we actually expect that any eavesdropper will know how we do the encryption; they just don’t know the key, which is the specific numbers we use to do it. Reversing this process (hopefully only done by the person you want to receive your message!) is called decryption. Sometimes you need a different set of numbers to decrypt, in which case we distinguish between the encryption key and the decryption key.
In the past, one would usually assume that both the sender and the receiver keep their keys secret (seems reasonable!), which is called symmetric key encryption. The symmetry is that both people need to keep it secret. One supposed early example of this goes back to C. Julius Caesar. To encrypt a message, first convert it to numbers, and then add three to each number (wrapping around if needed), and convert back to letters.
[13, 1, 20, 8, 9, 19, 3, 15, 15, 12] [13, 1, 20, 8, 9, 19, 3, 15, 15, 12] 
It's pretty clear that 1=A here, for instance. Now let's add three to each. The second letter should get to 4=D, for instance.
[16, 4, 23, 11, 12, 22, 6, 18, 18, 15] 'PDWKLVFRRO' [16, 4, 23, 11, 12, 22, 6, 18, 18, 15] 'PDWKLVFRRO' 
What did I do here? Well, this is really just modular arithmetic, modulo 26, so that is what I did.
How will I decrypt it, if I get this mysterious message? Here is the main point about mathematical ciphers; they need to come from operations that have inverses! So in number theoretic ciphers, they'll need to come from (somehow) invertible operations.
In this case, the operation is modular addition, which certainly has inverses. If your encoded numerical message is $x$, your key is $a$, and you are working modulo $(n)$, then your encrypted message $m$ is $$m\equiv x+a \text{ mod}(n)$$ To get $x$ back, you just use the additive inverse to $a$ modulo $n$, which is $a$.
Since $3$ is the inverse of $3$, this one is easy to decipher.
'MATHISCOOL' 'MATHISCOOL' 
We could list the key here as a pair $(a,n)$, with $a=3$ and $n=26$.
As noted above, one can do something similar with bigger numbers, in blocks of two.
[39, 228, 503, 393, 327] [39, 228, 503, 393, 327] 
Let's do something a little more interesting to encrypt this. What else has inverses?
Well, sometimes multiplication mod $(n)$ does! We could make a cipher that gets $m$ by performing $$m\equiv ax+b \text{ mod}(n)\; .$$ Here, let's choose $a=5$ and $b=18$; we'll use $n=677$, the next prime after $26^2$, since we have blocks of two letters each.
[213, 481, 502, 629, 299] 'EHMRHSEXMK' [213, 481, 502, 629, 299] 'EHMRHSEXMK' 
Now the key is listed as a triple, $(a,b,n)=(5,18,677)$. How do we invert this?
To get from $ax+b$ back to $x$, ordinarily we would subtract $b$ and then divide by $a$; but now we are working over $\mathbb{Z}_{n}$, so is that possible? We'll need our first `extra' condition; to make it workable, we need gcd$(a,n)=1$. In that case there is a number
$a'$ such that $$a(a')\equiv 1\text{ mod}(n)\; ,$$ so we can send $$m\to a'(mb)\equiv x\text{ mod}(n)\; .$$
To decode this particular example, then, we need to first subtract 18, then multiply by an inverse to 5 mod (677) (which turns out to be 271):
'MATHISCOOL' 'MATHISCOOL' 
The proof of the pudding is in the eating  there's no way I get the original message back unless this works!
There is another way of using blocks of size two or more, which we won't pursue, but which is a big piece of how standard encryption works (see here and here). Let's look at our message again.
[13, 1, 20, 8, 9, 19, 3, 15, 15, 12] [13, 1, 20, 8, 9, 19, 3, 15, 15, 12] 
Now, in blocks of two, I will change my numbers by turning the first one into the sum of the numbers modulo 26 and leaving the second one alone. So for the second block (20,8), I will change that block to (28,8), which modulo 26 becomes (2,8).
[14, 1, 2, 8, 2, 19, 18, 15, 1, 12] [14, 1, 2, 8, 2, 19, 18, 15, 1, 12] 
This turns out to be the same thing as multiplying the list of vectors of length two by the matrix $$\left(\begin{matrix}1& 1\\0& 1\end{matrix}\right)\; !$$ To invert this cipher, we would need an inverse to this matrix modulo 26. Another connection to the rest of mathematics! And a huge reason why linear algebra over finite algebraic structures is VERY important to security types.
Now, there is another type of encryption, which is rather different. There exists the possibility that everybody knows the key to encrypt, while only the legitimate person knows how to decrypt. This is called asymmetric key cryptography.
This may seem odd. But in practice today, people really do just post their encryption keys on the Internet! Here is one of someone you all know, for instance.
Then, in theory, anyone who wants to send Person XYZ a secure message could use this key, but only Person XYZ can decrypt it  convenient! Such a system is called publickey cryptography, although of course it's only the encryption key that is actually public.
We are not quite ready to talk about this yet. But we are ready to talk about a (symmetric) system that leads to it  one that really needs yet another invertible number theory procedure, one that we finally should be comfortable with. That procedure is modular exponentiation. Now that we can solve modular exponential using (for instance) primitive roots, we have the tools to tackle these far more subtle techniques. Let's go for it!
In the cell below, we will pick a few things. (Our secret is still that math is cool.) We need a prime number $p$, and some legitimate exponent $e$ that won't mess things up too badly. What do I mean by that? Remembering that when we solved $$x^{3}\equiv 5 \text{ mod}(17)\text{ as }3^{3i}\equiv 3^{5}\text{ mod}(17)$$ we ended up in the world of $\phi(17)=16$ and solving $$3i\equiv 5 \text{ mod}(16)\, .$$ In order to keep using this idea, we will pick an exponent coprime to $\phi(p)$.
Now, I just take my message and raise it to the $e$ power modulo $p$  simple as that!
[5, 1, 23, 15, 6, 11, 21, 26, 26, 12] 'EAWOFKUZZL' [5, 1, 23, 15, 6, 11, 21, 26, 26, 12] 'EAWOFKUZZL' 
Here I picked $p=29$, useful since it's close to 26, and more or less arbitrarily picked an exponent $e=9$. I still first had to encode 'MathIsCool' to numbers. Then I exponentiated each number in the coded version, modulo 29. To be precise, I sent each number $$a\to a^9\text{ mod }(29)\; .$$ (Notice that decoding the secret message code is not so useful anymore! So we usually just stick with the numbers.)
Leaving aside for the moment that the letter A will now have the unfortunate property that it always stays 1, and hence basically unencrypted (this is because we are doing a toy example), how on earth would we ever decrypt this? Do we have a way to invert $$a^9\text{ mod }(29)$$ in any way?
25 'MATHISCOOL' 25 'MATHISCOOL' 
Naturally, we do! We will use exponentiation again to do so. We just need something that solves $$\left(a^9\right)^f\equiv a\text{ mod }(29)\; ,$$ or more concisely $$a^{9f}\equiv a^1\text{ mod }(29)\; .$$ (We can think of $f$ as a power that inverts the original power $9$.). From our earlier discussion, this is just a solution to $$9f\equiv 1\text{ mod }(28)$$ and we know we can find this.
This method is known as the DiffieHellman, or DH, method (named after its originators, who proposed it in the mid70's). Now we will do a more real example of this. Notice how important it was that we chose an initial exponent $e$ that was coprime to $\phi(p)=p1$.
13044594485924740120065295822374 13044594485924740120065295822374 
For convenience, I'll just take the next prime bigger than my message.
13044594485924740120065295822453 2^2 * 3^2 * 11 * 17 * 8273 * 234219716629408326624607 13044594485924740120065295822453 2^2 * 3^2 * 11 * 17 * 8273 * 234219716629408326624607 
I factored $p1$ so I could find something coprime to it.
9687827625907130820812107474110 9687827625907130820812107474110 
The encrypted message is now just one number. Now we need the decryption key. Luckily, that's just as easy as taking an inverse modulo $p1$:
5098792796685815968933767514883 'HEYMATHISCOOLEVERYBODY' 5098792796685815968933767514883 'HEYMATHISCOOLEVERYBODY' 
Or a really cool example:
My encoded message is 456852583124842114039371869486849541361942257940969127 A big prime bigger than that is 19901253152869563309723662610292328389634458107944010604042555563705501076334500415727246558508890126813900283887956436979499141327004021398892610004731269986110529437289385314056563037068659842333714116396838715552272338731683607696792667582648188537035713642154015003 And I chose exponent 677 The encrypted message is 5671429597427784609252296012902402984799130703165480861885236311936909878124253596757140581626041120924645503439427869786950283574272896705647992202949606005119301174919954323984659002526192028827446976232112510529010204454970468780474512088807034775928563914920528081 The inverse of 677 is 17138006777138781993454793651108460046021992728111311938193219931521871680211246295966004052600713358836785621132464701268903987287508632903329972869657799707389126531668702567348561670031061577666994578817366279419460522127875248577887924964082561177388214259048435371 And the decrypted message turns out to be: MATHISREALLYCOOLANDITSHOULDNTBEASECRET My encoded message is 456852583124842114039371869486849541361942257940969127 A big prime bigger than that is 19901253152869563309723662610292328389634458107944010604042555563705501076334500415727246558508890126813900283887956436979499141327004021398892610004731269986110529437289385314056563037068659842333714116396838715552272338731683607696792667582648188537035713642154015003 And I chose exponent 677 The encrypted message is 5671429597427784609252296012902402984799130703165480861885236311936909878124253596757140581626041120924645503439427869786950283574272896705647992202949606005119301174919954323984659002526192028827446976232112510529010204454970468780474512088807034775928563914920528081 The inverse of 677 is 17138006777138781993454793651108460046021992728111311938193219931521871680211246295966004052600713358836785621132464701268903987287508632903329972869657799707389126531668702567348561670031061577666994578817366279419460522127875248577887924964082561177388214259048435371 And the decrypted message turns out to be: MATHISREALLYCOOLANDITSHOULDNTBEASECRET 
I'll ask you to do some by hand of this. Remember, our first awesome encryption scheme does the following:
Want to decrypt?
Feel free to see what happens with your own short messages.
Click to the left again to hide and once more to show the dynamic interactive window 
Homework to hand in:
