Hello everyone. Welcome to Week 8 of Carmen's Core Concepts. My name is Carmen Bruni. In these video series, I go through the content of the current week in Math 135, and try to give you a brief overview of what we covered. Again this isn't a substitute for lectures or anything like that, it's going to be very quick. The idea is to try to highlight the main points from the week, and to help you remember everything. I mean recalling things is very important in mathematics. So hopefully this videos give you a good recall of what we did this week.
So we talked about "the following are equivalent". We'll see what that is when we get to it. What I mean by this is we had a bunch of criteria for congruences and these list them all.
We talked about inverses, multiplicative inverses in $\mathbb{Z}_m$. We talked about the Linear Congruence Theorem, the second part to it. So where we reword it using our new notation with the equivalence classes. Then we talked about a couple of major theorems in this course: Fermat’s Little Theorem, Chinese Remainder Theorem and Splitting the Modulus. Then we wrapped up the week with a brief introduction to cryptography.
Again remember our goal is to head to RSA, which we'll do next week. Actually I’m probably going to isolate that in its own video, but here's the overview, and then I guess we finished off with the Square and Multiply Algorithm. It gives you a quick way to compute large powers of numbers to not necessarily prime moduli.
Let's start with the following proposition. So, we haven't seen this acronym yet, TFAE: the following are equivalent. So here we have a laundry list of things that are equivalent:
The following are equivalent:
Again, all of these are equivalent. One way to prove that things are equivalent is to, prove that so for example, $1 \Rightarrow 2 \Rightarrow 3 \Rightarrow 4 \Rightarrow 5 \Rightarrow 6 \Rightarrow 1$.
That's a very common way to do it, just prove everything is equal in a cycle. Sometimes if certain ones are harder, you might use if and only if statements so like $1 \Leftrightarrow 2$, and then you prove $1 \Rightarrow 3$, and $3 \Rightarrow 4$, and $4 \Rightarrow 1$, something like that is also possible too. Most of these are pretty straightforward though so you don't need to do anything fancy to prove this.
Let me just give you a quick example:
Solving $[10][x]=[1]$ is the exact same as solving $10x\equiv 1 \pmod m$
So these two are related. So for example if you have difficulties with this notation, bring it back down to $10x \equiv 1 \pmod m$, bring it to this notation, and it should be a little bit easier.
Inverses, so we spent a lot of time in the last two weeks talking about rings and fields, at least the general picture. We didn't talk anything too, too specific but I wanted to give you a big overview idea of some of the objects in abstract algebra: rings and fields.
And so we saw that in a ring, we have to have additive inverses of elements, okay, and in the case of $\mathbb{Z}_m$, the additive inverse is very simple. If you're dealing with the element $5$ in $\mathbb{Z}_m$, the additive inverse is $-5$.
Now you might want to shift that, for example, to make it positive by adding $m$. So $[m-5]=[-5]$, but either way is fine, and again remember that the additive inverse satisfies the property that $a+(-a)=0$. So whatever element this is when I add it to $a$ gives me $0$, that's the additive inverse.
Now multiplicative inverses we saw, and we'll deal with this in the next couple of slides, we saw that not all $\mathbb{Z}_m$ have multiplicative inverses.
So what is a multiplicative inverse? Well if $[a][b]=1=[b][a]$ - I've written down $[b][a]$ here just in case, in future courses, your ring might not be commutative. So you would have to at least examine both cases until you show that inverses are unique and things like that.
Here these are the same thing but anyways, if $[a][b]=1$, we call $[b]$ the multiplicative inverse of $[a]$ and we write $[b]=[a]^{-1}$, or sometimes we denote $b \equiv a^{-1} \pmod m$.
So something to think about here. $a^{-1}$, when you look at this, you should try to get away from thinking that this is $\displaystyle\frac{1}{a}$. That’s going to take a little bit of time to used to because you've thought about this as $\displaystyle\frac{1}{a}$ your whole life, but you should really be thinking of this as the element when I multiply it to $a$, it gives me $1$.
Now over the rational numbers let's say, that's equivalent to $\displaystyle\frac{1}{a}$. But in other rings like $\mathbb{Z}_m$ where we don't really have a notion of $\displaystyle\frac{1}{a}$, you have to be a little bit careful. So try to get yourself into that habit of rewiring your brain and saying, “Hey okay, $a^{-1}$, that's this number when I multiply it by $a$ gives me $1$.”
So again, multiplicative inverses. Multiplicative inverses don't always exist; depends on the $b$, it depends on the $m$, and let's talk about that.
Proposition: Let $a \in \mathbb{Z}$ and $m \in \mathbb{N}$.
So let's talk about this.
$$[a]^{-1}\, \text{exists} \Leftrightarrow [a][x]=[1]\,\text{is solvable in}\,\mathbb{Z}_m$$We can translate this, I guess using a couple of things, to the Linear Diophantine Equation that $ax+my=1$ is solvable.
$$\begin{align*} [a]^{-1}\,\text{exists} &\Leftrightarrow [a][x]=[1]\,\text{is solvable in}\,\mathbb{Z}_m\\\\ &\Leftrightarrow ax+my=1\,\text{is a solvable LDE [LCT1/LDET2]} \end{align*}$$So here $a$ and $m$ are fixed and $x$ and $y$ vary over the integers. So this has a solution if and only if $[a][x]=[1]$ is solvable in $\mathbb{Z}_m$. And then once we have this Linear Diophantine Equation, well we know this has a solution if and only if $\gcd (a,m)=1$, you can say by LDET1 or 2, or GCD Of One, all of these work.
$$\begin{align*} [a]^{-1}\,\text{exists} &\Leftrightarrow [a][x]=[1]\,\text{is solvable in}\,\mathbb{Z}_m\\\\ &\Leftrightarrow ax+my=1\,\text{is a solvable LDE [LCT1/LDET2]}\\\\ &\Leftrightarrow \gcd(a,m)=1 [GCDOO] \quad \blacksquare \end{align*}$$This is going to complete the proof. So what's the idea here? The idea here is that the inverse exists if and only if the above linear congruence is solvable, and linear congruence corresponds to a Linear Diophantine Equation, and that we've done a couple of theorems of earlier in the course.
Now to prove that it's unique, remember that if we want to prove that something is unique, just pretend that you have two elements that have the same property, and then show that they must be equal.
So in this case, we have that $[a]^{-1}$ exists and we're going to suppose there's some imposter element $[b]$ that satisfies the same criteria.
Then what can we do?
$$\begin{align*} [a][b]&=[1]\\\\ [a]^{-1}[a][b]&=[a]^{-1}[1] \end{align*}$$We're going to multiply both sides by this inverse element, $[a]^{-1}$. If we do that, what do we notice?
$$\begin{align*} [a][b]&=[1]\\\\ [a]^{-1}[a][b]&=[a]^{-1}[1]\\\\ [1][b]&=[a]^{-1}\\\\ [b]&=[a]^{-1} \quad \blacksquare \end{align*}$$So the inverse is unique if it exists. Okay so, key summary from this slide: inverse is unique, so this notation makes sense. The other thing that's important here is that the inverse exists if and only if $\gcd (a,m)=1$. So something to keep in mind.
For example, if $m$ were prime, then all elements not divisible by $p$, would be invertible. We actually call such things fields. So we say that $\mathbb{Z}_p$ is a field. We'll get to that in a couple of weeks again, but something to keep in mind for now.
So just rewarding, so Linear Congruence Theorem 2, so this is just a quick slide. We already have Linear Congruence Theorem 1, and this is just the statement of Linear Congruence Theorem 1, except in the equivalence class notation.
Theorem: Let $a,c \in \mathbb{Z}$ and let $m \in \mathbb{N}$. Let $\gcd (a,m)=d$. The equation $[a][x]=[c]$ in $\mathbb{Z}_m$ has a solution if and only if $d \mid c$. Moreover, if $[x]=[x_0]$ is one particular solution, then the complete solution is
$$\{[x_0],\left[x_0+\frac{m}{d}\right],\left[x_0+2\frac{m}{d}\right],...,\left[x_0+(d-1)\frac{m}{d}\right]\}$$So if you have one solution then you can find all solutions by adding multiples of $\displaystyle \frac {m}{d}$. How many multiples can we add to get unique elements? Well we can add up to $(d-1)$ of them.
So we've left the linear congruence theorem stuff a little bit. We'd like to go to sort of what I would consider two foundational theorems in the course: Fermat's Little Theorem and the Chinese Remainder Theorem.
So Fermat's Little Theorem, the proof of this, that we did in our class, is actually a little bit tricky. It's difficult to understand. I think it's a really nice proof, it's very clever, at least the one that we present. There are slightly…maybe I should say not less clever, but I would say differently clever proofs. This one's very easy to understand though, which is why I like it. It's not the easiest to do, I would say the easiest to do is using induction and the Binomial Theorem if you want to check that out, that'll be I think on Wikipedia actually. But anyways, Fermat's Little Theorem, let's talk about the theorem.
Theorem: If $p$ is prime and $p \nmid a$ then $a^{p-1} \equiv 1 \pmod p$. Equivalently, $[a^{p-1}]=[1]$ in $\mathbb{Z}_p$
Now the proof’s not going to fit on the slide and I don't think there's much value in doing it on 3 slides again, but let me just give you a recap of what the proof entailed. As long as you have the major elements, you can actually reconstruct this proof fairly easily.
There's two key sort of elements here, and the one key is this lemma and this is really important for this proof.
Lemma: Let $\gcd (a,p)=1$. Let
$$S=\{1,2a,...,(p-1)a\} \qquad T=\{1,2,...,p-1\}$$Then the elements of $S$ are unique modulo $p$ and for all $s \in S$, there exists a unique element $t \in T$ such that $s \equiv t \pmod p$.
What's really happening here? What's really happening here is that the element $a$ is invertible. So one way to look at this is you can set up a map from $S$ to $T$ and you look at $S$ and $T$ as subsets of $\mathbb{Z}_p$, and you can set up a map from $S$ to $T$ defined by sending an element $s$ to the element $s \cdot a^{-1}$, for example, and that sets up a bijection between $S$ and $T$. That’s one way to look at this.
Another way is just to go through it. All the elements of $S$ are non- zero $\bmod p$, and all of them are distinct $\bmod p$, so therefore they must be equal to $t \bmod p$, in some rearrangement.
Why is this important? Why is this $S$ and $T$ important?
$$\prod_{x \in S} x \equiv \prod_{y \in T} y \pmod p$$And why is that? Let's think about that. If you take $\displaystyle \prod_{x \in S} x$ and $\displaystyle \prod_{y \in T} y$, well we said before that these two sets are equal $\bmod p$, up to a rearrangement. So if I multiply them together, because of commutativity, it doesn't matter.
What do I mean by, “it doesn't matter”? Well I mean that the product of the elements in $S$ must be the same as the product of the elements of $T$. Right? Because, again, $S$ and $T$ are the same $\bmod p$ up to a rearrangement.
So what does this mean? What do the elements of $S$ look like?
$$\prod_{x \in S} x \equiv \prod_{y \in T} \pmod p \Leftrightarrow \prod_{k=1}^{p-1} ka \equiv \prod_{j=1}^{p-1} j \pmod p$$Well they look like multiples of $a$, so let's write down multiples of $a$. And what do the elements of $T$ look like? Well they look like the integers from $1$ to $(p-1)$, so let's write that down.
Now if I'm doing this product here, $\displaystyle \prod_{k=1}^{p-1} ka$, well $a$ is getting multiplied $p-1$ times, so it's the same as multiplying by $a^{p-1}$ times $\displaystyle\prod_{k=1}^{p-1} ka$.
$$\begin{align*} \prod_{x \in S} x \equiv \prod_{y \in T} \pmod p &\Leftrightarrow \prod_{k=1}^{p-1} ka \equiv \prod_{j=1}^{p-1} j \pmod p\\\\ &\Leftrightarrow a^{p-1} \prod_{k=1}^{p-1} k \equiv \prod_{j=1}^{p-1} j \pmod p \end{align*}$$The same thing with the product of $j$, I didn't touch that side. Note though that these products, these are actually just a clever notation for $(p-1)!$, well we know that $p$ is prime, and so $(p-1)!$ and $p$ don't share any common factor. So because $p$ is prime and its only divisors are $1$ and $p$, so no number less than $p$, other than $1$, divides $p$ and $(p-1)!$ ,so therefore $\gcd (p,(p-1)!)=1$. Because of that, I can cancel since they're invertible that was a previous theorem.
$$\begin{align*} \prod_{x \in S} x \equiv \prod_{y \in T} \pmod p &\Leftrightarrow \prod_{k=1}^{p-1} ka \equiv \prod_{j=1}^{p-1} j \pmod p\\\\ &\Leftrightarrow a^{p-1} \prod_{k=1}^{p-1} k \equiv \prod_{j=1}^{p-1} j \pmod p\\\\ &\Leftrightarrow a^{p-1} \equiv 1 \pmod p \quad \blacksquare \end{align*}$$And that's it. A clever, clever statement, so now the proof is one thing. I mean, do we really expect you to know all these things? *shrugs* I'll let you decide based on that reaction. But what's really important about Fermat’s Little Theorem is the ability to apply it, and we're going to see an application right now.
Find the remainder when $7^{92}$ is divided by 11.
So again, a good point, at this point, to actually try this problem. You should try it.
When you're looking at $7^{92}$, well okay $11$ is a prime, and we know that $11 \nmid 7$. Why is that important? If $11 \mid 7$, the answer would be really easy. If $11 \mid 7$, then $11 \mid 7^{92}$ and so we get that this is congruent to $0 \bmod 11$.
So when finding the remainder, again remember by CISR, Congruent If and Only If Same Remainder, we can look at this $\bmod 11$, reduce it to the least non-negative residue, and then argue by CISR that since those numbers are congruent $\bmod 11$, then the original number and the last number must have the same remainder when divided by $11$, and the least non-negative residue $\bmod 11$ is actually just the remainder. When this number is divided by $11$.
So again what do I know by Fermat’s Little Theorem? I know that because $11$ is co-prime to $7$, $7^{11-1}=7^{10} \equiv 1 \pmod {11}$.
So what am I going to try to do with $7^{92}?$ I'm going to try to get $7^{10}$ to appear. And the way I like to do this - so there's a lots of ways. You actually start with $7^{10}$, and then take it to the power of $9$, and then multiply by $7^2$, that's one way to do it.
The way I like to start though is because usually when you're solving these problems, you have a sum of these numbers and you're dealing with multiple things, so I like using this method a little bit more. Personal preference of course.
$$\begin{align*} 7^{92}&\equiv 7^{9(10)+2} \pmod {11}\\\\ &\equiv (7^{10})^97^2 \pmod {11}\\\\ &\equiv 1^9 \cdot 7^2 \pmod {11}\\\\ &\equiv 49 \pmod {11}\\\\ &\equiv 5 \pmod {11} \end{align*}$$By CISR, the remainder when I divide $5$ by $11$ is $5$, so therefore the remainder when I divide $7^{92}$ by $11$ is $5$, since $7^{92} \equiv 5 \pmod {11}$. And that's it.
So a fun little example. These questions are actually fun once you get use of them, but they do take a little bit of time. So don't be discouraged if at first you don't see all these patterns and stuff, but do practice, do take a couple of examples. Create your own examples, there are lots of computer programs that can compute this very quickly, so the chances of you writing a small example and not being able to verify it on a computer are very small. This is worth doing for your first attempt.
Corollaries to F$\ell$T, so some of these I like to use a lot. So that's why I've put them all on the board. I've put them all on one slide. They're not too hard to prove, I didn't prove any in this talk, but you can check them out in the notes online.
Corollary: If $p$ is a prime and $a \in \mathbb{Z}$, then $a^p \equiv a \pmod p$
So how does this one work? So when $p \nmid a$, this is just F$\ell$T and then multiplied by $a$, and when $p \mid a$, well $a \equiv 0 \pmod p$. So $a^p \equiv 0 \pmod p$, and so these two numbers must be equal.
Corollary: If $p$ is a prime number and $[a]\neq 0$ in $\mathbb{Z}_p$, then there exists a $[b] \in \mathbb{Z}_p$ such that $[a][b]=[1]$, namely $[b]=[a^{p-2}]=[a]^{p-2}$.
Again so what things does this use? So $p-2 \geq 0$, because $p$ is a prime number, so this actually makes sense. And what do we know here? So if I take $[a][a]^{p-2}$, that's just $[a]^{p-1}$, and that's $1$ by F$\ell$T. We know that $[a]$ is not the same as $0$ in $\mathbb{Z}_p$.
Corollary: If $r=s+kp$, then $a^r \equiv a^{s+k} \pmod p$ where $p$ is a prime and $a \in \mathbb{Z}$ and $r,s,k \in \mathbb{N}$
Again, this just uses the first corollary. Notice that $r,s,k$ are natural numbers and the reasons why is that you get some weird situations. So if $r$ was negative, let's say, then I have $a^r=(a^{-1})^r$, but I don't know that $a$ is invertible. So I need to be a little bit careful here. But again the proof is actually just identical to the corollary above - well the proof just uses the corollary above, it's not identical but it uses that corollary.
Corollary: Prove that if $p \nmid a$ and $r \equiv s \pmod {(p-1)}$, then $a^r \equiv a^s \pmod p$
So here we allow $r$ and $s$ to be negative, which is not a problem because $a$ is invertible $\bmod p$. That's a slight subtlety, something to think about, maybe on the bus. Why can't we really do this over the integers, in general.
This is the simplified Chinese Remainder Theorem. The generalized one just uses more equations, but the idea reduces to the two equation Chinese Remainder Theorem. So let me just give you the two equation Chinese Remainder Theorem:
Theorem: If $\gcd(m_1,m_2)=1$, the for any choice of integers $a_1$ and $a_2$, there exists a solution to the simultaneous congruences
$$\begin {align*} n &\equiv a_1 \pmod {m_1}\\\\ n &\equiv a_2 \pmod {m_2} \end{align*}$$Moreover, if $n=n_0$ is one integer solution, then the complete solution is $n \equiv n_0 \pmod {m_1m_2}$
So super powerful theorem; it says a couple of things. One that this has a solution, and it always has a solution if $m_1$ and $m_2$ are co- prime.
One thing to note, this is the first time that we've used different moduli. So up to this point, we've always been looking at, let's say, a linear congruence, which has only used $1$ moduli, but now we have $2$. So this is the first time we're interplaying $2$ moduli.
Moreover, what does this say? Well if we have $1$ solution, then we can find all solutions. So buy $1$, get infinitely many for free is what I like to look at these theorems as, okay? So if I have 1 solution, I can find them all by just taking the product of the moduli and looking at $n \equiv n_0 \pmod {m_1m_2}$.
This is one of these theorems where the proof is actually basically given by an example. You can do it abstractly, which is fine, but it basically is just do an example and go through it, which I think I'm going to do on the next slide.
Solve the simultaneous congruence
$$x \equiv 2 \pmod 7 \quad x \equiv 7 \pmod {11}$$Now if you’re looking at this for the first time, take a minute, actually make sure you can do this. Try to solve this problem.
So when we're solving these simultaneous congruences, what I like to do is I like to start with the bigger number. I'm going to start with the $\bmod 7$ in my solution, but it actually helps to start with a bigger number, usually because when I go to the smaller number $\bmod 7$, it's easier to reduce. But, however, that’s not the way I'm going to do it. I'm going to start left to right, which is perfectly fine as well. You just might have to deal with harder computations $\bmod {11}$. Something to think about.
$x \equiv 2 \pmod 7$, we use TFAE to write $x=2+7k$ for some $k \in \mathbb{Z}$. Then we plug this $x$ into the second equation, and we simplify
$$\begin{align*} 2+7k &\equiv 7 \pmod {11}\\\\ 7k &\equiv 5 \pmod {11} \end{align*}$$So here we brought the $2$ over to the other side. Now when we get to this point, there's lots of ways to approach this. One way to do this, if you don't see an immediate answer, you can turn this to a Linear Diophantine Equation, you can solve it. You can try to guess the answer for $k$, right, because this is a linear congruence and once we know one answer we know all of them. I know that $\gcd(7,11)=1$, $1 \mid 5$, so there is a solution by LCT1, and there's exactly 1 solution $\bmod 11$. So once you find one value for $k$, it's good.
Another way to do that, the way I like to look at this is I like to look at this as I'm trying to divide by $7$, right, that's what I would do over if it was an equal sign. So remember that we don't really have division, but we do have multiplication by the inverse, which you should think of as the same as division. So multiplying by the inverse, which we know exists, again since the $\gcd(7,11)=1$, so we try to find the inverse.
Turns out that the inverse to $7$ is $8$. $8 \times 7=56$, but $8 \equiv -3 \pmod {11}$. And one thing to notice, if I multiply this equation by $3$ on both sides, which is valid by Properties of Congruence, let's say. What does that give me?
$$\begin{align*} 3 \cdot 7k &\equiv 5 \cdot 3 \pmod {11}\\\\ 21k &\equiv 15 \pmod {11}\\\\ -k &\equiv 4 \pmod {11}\\\\ k &\equiv 7 \pmod {11} \end{align*}$$So therefore, $k=7+11l$, for some $l \in \mathbb{Z}$, and since $x=2+7k$ and $k=7+11l$,, we can substitute the $k$ value into the $x$ equation and what do we get?
$$x=2+7k=2+7(7+11l)=51+77l$$And a couple of ways to think about this, so what does this mean? So $x=51+77l$. $x$ was some arbitrary solution at the beginning. So no matter what solution we pick, $x=51+77l$. And it's very quick to see that all of these are actually solutions to this, and therefore $x\equiv 51 \pmod {77}$ gives the complete solution set.
So there's a little bit of a step there to get the logic around because we are doing things like oh well we're taking for some $l$, and then we're getting rid of it, and then we're claiming that all of these are solutions, so there's a little bit to think about there. But I don't want to get too bogged down by those details. I’d rather you think, “Okay, well if I started with a solution $x$, and each of these $51+77l$ are solutions to this equation.” And that's it.
So that's the Chinese Remainder Theorem. Now you can do this with, instead of $2$ equations, $3$ equations, and $4$ equations, all that's fine. Just take $2$ of them, simplify it, and then take the next $2$ and simplify it, and so on and so forth. So it's not any harder to do this with more equations. Well it's more work, but it's not mentally harder. And there are a couple twists that we saw in class, but I don't believe I'm going to go through them now, no I'm not. For the extra twists and things that we can do to…not trick you but to…let me just say trick you even though it’s not true. To make it more complicated. So things that we do to make it more complicated, you can check those out on the website.
Splitting the Modulus, this was the last thing we talked about. I had a student ask a good question this week and they said, “Well okay so if we have the Chinese Remainder Theorem, it's like we're combining moduli,” and the student asked, “Well can we break them apart?” And I said well yes absolutely we can, in certain cases. That's we're going to talk about here with Splitting the Modulus.
Theorem (SM): Let $m$ and $n$ be coprime positive integers. Then, any integers $x$ and $a$, we have
$$\begin{align*} x &\equiv a \pmod m\\\\ x&\equiv a \pmod n \end{align*}$$simultaneously if and only if $x \equiv a \pmod {mn}$
Note that $m$ and $n$ are coprime integers. So again that's really important.
The proof in one direction is just the Chinese Remainder Theorem, right, $x=a$ is a solution to the simultaneous congruence so therefore $x \equiv a \pmod {mn}$ gives us the full solution by the Chinese Remainder Theorem.
To go the opposite direction, it actually turns out to be an argument in transitivity. So $mn \mid (x-a)$, and $m \mid mn$, so therefore $m \mid (x-a)$, that's the first equation. Similarly for $n$.
Actually a very simple theorem to prove. This is pretty powerful when you can actually get the $x$ congruent to the same $a$ $\bmod m$ and $\bmod n$. Sometimes you can do it by guessing, which is pretty neat. It's not often, but sometimes you can. If the numbers are small, you should be able to guess the solution fairly quickly. If the numbers are big, you should try to use the Chinese Remainder Theorem, use Linear Diophantine Equation stuff, the Extended Euclidean Algorithm, things like that to get you the answer very quickly.
But anyways here it is; Splitting the Modulus. So we've seen some examples in class, I don't think I'm going to do any here. Again check the notes for some examples of the use of this. You'll actually see it though in RSA, at least in the proof of RSA, next week.
This is what we ended our week on. What is cryptography? That's a good question, cryptography can be viewed as the practice or study of secure communication. That's basically what cryptography is. The idea is that I want to send secure messages to somebody that I possibly know or don't know.
So for example, if I want to talk to a bank. I might not necessarily know who I'm talking to in the bank or exactly, you know, who's on the other end, but I do know that it's the bank that I'm trying to communicate with. And the bank knows me but doesn't really know me, you know, I mean they don't know that I want to communicate. So there has to be some way that I can tell the bank, “Hey I'm ready to talk now,” and then we can try to talk, okay?
So you can imagine like a phone call, but of course we were in the digital age, right? We have the internet and things like that, so you can imagine doing online banking stuff and things like that. And we talked a little bit about private versus public key cryptography.
So the idea behind private key cryptography is that a private key is shared between two people.
So the example that we use is the story of Caesar and the Romans. So Caesar would encrypt messages using something called the Caesar Cipher, and he took letters and shifted them by $3$. So for example, a mapped to d, b mapped to e, c mapped to f and so on and so forth.And he did the loop around as well. So for example, x mapped to a, y mapped to b, and z mapped to c.
This worked very well in Rome because well most soldiers were illiterate so even if it was written in Latin or whatever language they used, they probably wouldn’t be able to read it anyways, but then the few soldiers who were literate still couldn't read it because they shifted the letters by a bit so they just would, you know, instead of trying to read the messages, they would just rip them up and burn them. They could have gained a lot of information if they knew how the messages were encrypted.
That's the idea behind private key cryptography, however of course the problem with this is that you have to somehow exchange to another person that oh hey this is my private key. But if I don't really know the other person, like if it's just some big bank, you can imagine this being a very, very long and arduous procedure to watch to the bank and be like, “Hi, this is my private key that I'm going to use today,” then go back home and then try to communicate online. I mean that's kind of…that's slow, and if you imagine doing this with like a billion people, you're storing at least a billion private keys. That's a lot of keys to keep in mind.
But public key cryptography is the idea that we don't need to do this. Or at least we can limit how much we do this. The idea is the padlock analogy. So remember from, let's say high school right, when you would lock your locker up with a lock. To lock it is very easy, right? If I gave you an open padlock, you would put it in your lock and then close it, okay? So it's very easy to lock a padlock, but to unlock it, you actually need to know the key. And that's the idea behind public key cryptography. You make certain information public, you make the encryption process public, but you make the decryption process private.
So let's see the general scheme, and we'll talk about this a lot more with the RSA cryptography scheme.
So Alice produces a private key $d$ and a public key $e$. The idea is that the public key is for everyone to know, and the private key is used for decryption and only Alice knows it, okay, and the idea is that there's some eavesdropper, Eve, that's watching all the communication. So Eve can see this public key, $e$. I use Eve instead of Oscar. Personal preference by the way.
Now Bob uses this public key, $e$, to take a message $M$, he does something to $M$ with $e$ and encrypts it to get some ciphertext, $C$. So let's say my message is “Hello” and the public key tells me to, I don't know, scramble the letters around, and so I get my ciphertext let's say, “OLLEH”. It doesn't have to be just a rearrangement, it can be like you changed letters, like we did in the cipher or the Caesar Cipher, I'm trying to give you an example.
Bob then sends $C$ over an insecure channel to Alice. So again, Eve can see $C$, so Eve sees $e$ and Eve sees $C$. Then Alice decrypts $C$ to $M$ using $d$.
So the idea is that the eavesdropper doesn't know $d$, and hopefully decrypting and finding $M$ from just $C$ and $e$ is actually difficult. That's the hope here.
What are the key important facts to this? Encryption, decryption are inverses to each other. So Bob is trying to send a message to Alice, so Bob takes some message, encrypts it, sends it to Alice. You need to decrypt it to get back to the message, $M$, that Bob had. They must be inverses. If Alice decrypts it and gets some message that's not $M$, that's a problem, okay, so encryption, decryption must be inverses.
$d$ and $e$ are different numbers. It would be silly if your public key was the same as your private key, then everyone could decrypt it.
Only $d$ is secret, okay? So only your private key is secret. So we'll see how to actually do this using modular arithmetic with RSA. But for now, just kind of keep the general framework in mind of public key cryptography and when we see RSA in next week's video, it'll give you a little bit of context.
Last thing I want to talk about is the Square and Multiply Algorithm.
Compute $5^{99} \pmod {101}$.
So if you haven't seen this, this is actually somewhat of an optional topic in Math 135. At least it was when when I taught it in the year 2015-2016. This could be different now.
So the first thing I'd like you to do is actually try this. Try to compute $5^{99}$, and if you haven't seen the Square and Multiply Algorithm, let me give you just the baseline of it or what's going to happen. What we're going to do is we're going to compute $5$ to the powers of $2$. So we're going to compute $5^1,5^2,5^4,5^8,5^{16},5^{32},5^{64}$.
Once we do that, we're going to write $99$ in binary, so we're going to write $99$ as a sum of powers of $2$. Once you write $99$ as a sum of powers of $2$, we're going to combine those two pieces of information together and get a result for $5^{99} \pmod {11}$. Give it a shot.
So as promised, we're going to compute successive powers of $5$. So we're going to square them, this is the squaring part of “square and multiply”.
$$\begin{align*} 5^1&\equiv 5 \pmod {101}\\\\ 5^2&\equiv 25 \pmod {101}\\\\ 5^4&\equiv (25)^2 \equiv 625 \equiv 19 \pmod {101}\\\\ 5^8&\equiv (19)^2 \equiv 361 \equiv 58 \pmod {101}\\\\ 5^{16}&\equiv (58)^2 \equiv 31 \pmod {101}\\\\ 5^{32}&\equiv (31)^2 \equiv 52 \pmod {101}\\\\ 5^{64}&\equiv (52)^2 \equiv 78 \pmod {101} \end{align*}$$These numbers are big so you probably want to use a calculator, I guess I should have mentioned that. Yeah so I mean, a calculator here is important. Why am I saying to use a calculator? The reason why I want us to use a calculator is because this is actually used when you have like, let's say for example, well $101$ happens to be prime, but if you have non prime moduli, this is actually how you can compute very large powers very quickly. You don't need to do too many operations.
Naively, you would have to do $5^{99}$ , and you'd have to reduce $\bmod 101$ each time so the numbers don't get too big. What the Square and Multiply Algorithm is doing is it's actually saying hey instead of doing this operation $5^{99}$, let's be a little bit clever and split this up into powers of $2$, and then pick the correct powers of $2$ to multiply together.
So if you look right now, how many operations have we done? I'd say around $14$ operations. Then now what we're going to do is we're going to write $99$ as a sum of powers of $2$, so in binary. So if you don't know how to write things in binary, I suggest googling this.
But the main idea is taking $99$, finding the highest power of $2$ less than it, subtracting it from that number, and then repeating that process.
$$99=64+32+2+1=2^6+2^5+2^1+2^0$$So now if I look at $5^{99}$, well $5^{99}$, just by this operation here, is:
$$5^{99}\equiv 5^{64} \cdot 5^{32} \cdot 5^2 \cdot 5^1 \pmod {101}$$But we know all of these numbers. We know $5^{64}$, we know $5^{32}$, we know $5^2$, and we know $5$.
$$\begin{align*} 5^{99}&\equiv 5^{64} \cdot 5^{32} \cdot 5^2 \cdot 5^1 \pmod {101}\\\\ &\equiv 78 \cdot 52 \cdot 25 \cdot 5 \pmod {101}\\\\ &\equiv 81 \pmod{101} \end{align*}$$So this binary operation thing, let's say it adds another $3$ or $4$ operations, and let's say this $5^{99}$ thing, we have $3$ more multiplications, one more reduction maybe, say about $20$ operations.
Normally the number of operations would be, like I said right, $99$ let's say times $2$, be a little bit, accounting for rounding error, let's say about $200$ computations and we turned that to about $20$ computations, okay? So we're saving by a factor of $10$, that's a lot.
So naively, it would take I believe linear amount of time, and using the Square and Multiply Algorithm takes logarithmic amount of time. So huge savings in the time that it takes to compute these things. This is important because we use the Square and Multiply Algorithm in RSA. It'll turn out that computing number exponents, or numeric exponentiation, is actually an important operation in RSA and we want that operation to be quick. So that's why we have this.
Okay, I think that's all I have to say for today. Thank you very much for listening to Week 8 and good luck in your studies.