WEBVTT
1
00:00:00.000 --> 00:00:04.600
We spent yesterday talking about Euclid's algorithm and greatest common divisors.
2
00:00:04.600 --> 00:00:08.960
And going through some basics of number theory, understanding the idea of arithmetic
3
00:00:08.960 --> 00:00:11.080
modulo other numbers.
4
00:00:11.080 --> 00:00:14.680
And what we're going to do today is kind of build on that, go through one of the
5
00:00:14.680 --> 00:00:20.080
nice elementary theorems in number theory, which turns out to be, it's very abstract
6
00:00:20.080 --> 00:00:22.400
theorem, it's very interesting, it's very elegant.
7
00:00:22.400 --> 00:00:26.760
But it turns out that nowadays it's at the heart of what makes these
8
00:00:26.760 --> 00:00:29.760
public key cryptography systems work.
9
00:00:29.760 --> 00:00:33.600
And we're going to go through this theorem, leave it on the side, make sure everybody
10
00:00:33.600 --> 00:00:34.600
understands what it says.
11
00:00:34.600 --> 00:00:36.600
We're going to prove it because it's a nice proof.
12
00:00:36.600 --> 00:00:40.200
And then we're going to switch gears and talk about cryptography as a topic, as a
13
00:00:40.200 --> 00:00:41.200
subject.
14
00:00:41.200 --> 00:00:42.600
And there's a lot to talk about.
15
00:00:42.600 --> 00:00:44.400
You can do a whole course in it.
16
00:00:44.400 --> 00:00:47.640
I'm just going to give you a little brief history of how people used to encode things
17
00:00:47.640 --> 00:00:49.480
and decode things.
18
00:00:49.480 --> 00:00:53.720
And then jump right into how people do it today.
19
00:00:53.720 --> 00:00:59.440
And basically the way people do it today is extremely secure is a way which is virtually
20
00:00:59.440 --> 00:01:00.520
unbreakable.
21
00:01:00.520 --> 00:01:06.120
And the reason it's unbreakable is based on the fact that nobody knows any good algorithm
22
00:01:06.120 --> 00:01:10.800
to factor very, very large numbers into their primes.
23
00:01:10.800 --> 00:01:15.640
If somebody had a good algorithm to do that, then all these cryptography methods that are
24
00:01:15.640 --> 00:01:20.200
popular nowadays would crumble and be easily breakable.
25
00:01:20.200 --> 00:01:25.880
And you'll see why you need to factor large numbers in order to break this code.
26
00:01:25.880 --> 00:01:29.600
And until somebody comes up with any method of factoring large numbers at works, these
27
00:01:29.600 --> 00:01:34.600
codes are going to be essentially completely secure.
28
00:01:34.600 --> 00:01:38.560
By the way, it's not known whether factoring large numbers is really a hard problem.
29
00:01:38.560 --> 00:01:43.400
Nobody knows whether it's NP complete and nobody's got any good algorithms for doing
30
00:01:43.400 --> 00:01:44.400
it.
31
00:01:44.400 --> 00:01:46.080
There's a lot of research that goes into that.
32
00:01:46.080 --> 00:01:50.240
There are probabilistic algorithms for trying to determine whether a number's primary
33
00:01:50.240 --> 00:01:52.240
not.
34
00:01:52.240 --> 00:01:55.760
Algorithms that don't necessarily tell you the right answer accept they got a good chance
35
00:01:55.760 --> 00:01:57.480
of telling you the right answer.
36
00:01:57.480 --> 00:02:01.440
So if you run them a lot, you get a pretty good sense of whether the number's primary
37
00:02:01.440 --> 00:02:03.160
you don't know for sure.
38
00:02:03.160 --> 00:02:08.400
You know for sure within one tenth of a percent margin of error.
39
00:02:08.400 --> 00:02:10.000
That doesn't tell you how to factor the number.
40
00:02:10.000 --> 00:02:11.640
That just tells you whether it's primary not.
41
00:02:11.640 --> 00:02:15.680
But actual factoring is a hard problem that nobody's got a good algorithm for, sort of
42
00:02:15.680 --> 00:02:19.560
trying all the possibilities and that's just too slow for the large numbers we're talking
43
00:02:19.560 --> 00:02:20.560
about.
44
00:02:20.560 --> 00:02:21.800
So that's where we're headed.
45
00:02:21.800 --> 00:02:25.520
The history of cryptography a little bit talking about where it started, where it ends
46
00:02:25.520 --> 00:02:30.520
up, where we are today, why it connects the number theory and then doing some examples.
47
00:02:30.520 --> 00:02:33.440
Okay, questions.
48
00:02:33.440 --> 00:02:34.720
Here we go.
49
00:02:34.720 --> 00:02:40.520
So we're going to start with a nice theorem that it's all based on.
50
00:02:40.520 --> 00:02:46.200
Here's called from us theorem or from us little theorem.
51
00:02:46.200 --> 00:02:52.600
This is to distinguish it from from us last theorem, which is more famous.
52
00:02:52.600 --> 00:02:55.280
Here's what from us says.
53
00:02:55.280 --> 00:03:10.080
He says take a prime number p and let a be any number.
54
00:03:10.080 --> 00:03:18.680
Not the visible by p.
55
00:03:18.680 --> 00:03:19.880
Here's what his theorem says.
56
00:03:19.880 --> 00:03:28.880
Then a to the p minus 1 is congruent to 1 not p.
57
00:03:28.880 --> 00:03:29.880
That's the theorem.
58
00:03:29.880 --> 00:03:30.880
There it is up in the board.
59
00:03:30.880 --> 00:03:33.400
I'm sure it's in your book as well.
60
00:03:33.400 --> 00:03:36.720
It's in a pretty much every number theory book.
61
00:03:36.720 --> 00:03:40.920
Look at it and try to figure out what it says in the meantime I'll do an example and you're
62
00:03:40.920 --> 00:03:43.480
already know what it says if you look at the example.
63
00:03:43.480 --> 00:03:44.720
Let's pick a prime number.
64
00:03:44.720 --> 00:03:46.960
Let's say pick your favorite prime.
65
00:03:46.960 --> 00:03:48.200
I'll pick it.
66
00:03:48.200 --> 00:03:49.200
I'll pick it.
67
00:03:49.200 --> 00:03:51.120
Yeah, you get five.
68
00:03:51.120 --> 00:03:54.200
Five is my favorite prime.
69
00:03:54.200 --> 00:03:56.480
Pick any number that's not the visible by five.
70
00:03:56.480 --> 00:03:59.720
Let's say six.
71
00:03:59.720 --> 00:04:01.640
This theorem says that six.
72
00:04:01.640 --> 00:04:12.640
So six is a, five is p. This says that six to the fourth is congruent to one mod five.
73
00:04:12.640 --> 00:04:20.440
Six to the fourth is 1296.
74
00:04:20.440 --> 00:04:23.440
1296?
75
00:04:23.440 --> 00:04:24.440
1296.
76
00:04:24.440 --> 00:04:25.440
1296.
77
00:04:25.440 --> 00:04:28.320
And if you divide through by five you get a remainder of one.
78
00:04:28.320 --> 00:04:30.160
So I want to make sure everybody knows this notation.
79
00:04:30.160 --> 00:04:31.800
This means congruent to one mod five.
80
00:04:31.800 --> 00:04:34.240
That means when you divide by five you get a remainder of one.
81
00:04:34.240 --> 00:04:36.360
That's what that notation means.
82
00:04:36.360 --> 00:04:38.160
Okay, that's what the theorem says.
83
00:04:38.160 --> 00:04:40.520
And it's true and it always works.
84
00:04:40.520 --> 00:04:42.520
And the question is why does it always work?
85
00:04:42.520 --> 00:04:46.760
And we're going to try to prove it and get an idea if you understand the proof great.
86
00:04:46.760 --> 00:04:49.800
If you don't understand the proof it won't affect your understanding of anything after
87
00:04:49.800 --> 00:04:50.800
it.
88
00:04:50.800 --> 00:04:53.320
So make sure you understand the fact that the theorem's true.
89
00:04:53.320 --> 00:04:56.480
We'll work on the proof for about five minutes or so and then we'll move on to cryptography.
90
00:04:56.480 --> 00:04:58.480
Where is the six coming from?
91
00:04:58.480 --> 00:05:03.040
I just picked it out of a hat. It's any number A that's not the visible by P. Let's try
92
00:05:03.040 --> 00:05:05.480
another number.
93
00:05:05.480 --> 00:05:10.680
11 to the fourth.
94
00:05:10.680 --> 00:05:13.280
Well that also ends in one, right?
95
00:05:13.280 --> 00:05:15.240
So some of these are easy to see.
96
00:05:15.240 --> 00:05:16.240
Some are harder to see.
97
00:05:16.240 --> 00:05:20.120
I pick five because it's easy to see that it's true usually.
98
00:05:20.120 --> 00:05:23.960
Because it's lower in less than P.
99
00:05:23.960 --> 00:05:26.080
Which is three two.
100
00:05:26.080 --> 00:05:27.960
Oh, that should work.
101
00:05:27.960 --> 00:05:31.920
As long as it's not the visible by P, anything less than P should work.
102
00:05:31.920 --> 00:05:35.720
You know, four to the fourth.
103
00:05:35.720 --> 00:05:38.720
What's that?
104
00:05:38.720 --> 00:05:43.360
Four to the fourth is two fifty six.
105
00:05:43.360 --> 00:05:44.360
Yeah.
106
00:05:44.360 --> 00:05:45.360
Yeah.
107
00:05:45.360 --> 00:05:48.200
Now it should work fine for things less than P. Other questions.
108
00:05:48.200 --> 00:05:49.200
All right.
109
00:05:49.200 --> 00:05:53.120
So why is this true?
110
00:05:53.120 --> 00:05:54.760
The proof is really kind of clever.
111
00:05:54.760 --> 00:06:00.080
And it's a good example of how you can kind of come up with very interesting theorems
112
00:06:00.080 --> 00:06:04.680
and the argument as to why the truth is really, really elegant.
113
00:06:04.680 --> 00:06:07.600
So I'm going to do this argument in its generality.
114
00:06:07.600 --> 00:06:10.720
I usually do arguments with particular examples.
115
00:06:10.720 --> 00:06:12.080
So I think they're easy to understand.
116
00:06:12.080 --> 00:06:15.240
But I don't think you'll miss the point if I do this in general.
117
00:06:15.240 --> 00:06:16.800
So here's what we're going to do.
118
00:06:16.800 --> 00:06:17.640
And follow me along.
119
00:06:17.640 --> 00:06:24.600
We're going to, I'm going to convince you that in general, P is going to divide evenly
120
00:06:24.600 --> 00:06:27.560
into a to the P minus 1 minus 1.
121
00:06:27.560 --> 00:06:31.280
But if I take this one away from here, then people divide evenly there.
122
00:06:31.280 --> 00:06:34.560
That's the same as showing that there's a remainder of 1 when I divide by P.
123
00:06:34.560 --> 00:06:35.520
So how am I going to do that?
124
00:06:35.520 --> 00:06:36.960
Here's how we're going to start.
125
00:06:36.960 --> 00:06:39.520
I'm going to start out considering the sequence of numbers.
126
00:06:39.520 --> 00:06:47.520
A, 2, A, 3, A, all the way up to P minus 1 times A.
127
00:06:47.520 --> 00:06:48.600
Just consider this sequence.
128
00:06:48.600 --> 00:06:56.040
In the example we just did, that would be 6, 12, 18, 24.
129
00:06:56.040 --> 00:07:01.720
We'd go up to 4 times 6, 6, 12, 18, 24.
130
00:07:01.720 --> 00:07:09.720
Maybe I should do a specific example while I do the general example.
131
00:07:09.720 --> 00:07:14.240
Look at these numbers with respect to 5.
132
00:07:14.240 --> 00:07:16.400
What are the remainders of these numbers with respect to 5?
133
00:07:16.400 --> 00:07:18.560
Let's write them down.
134
00:07:18.560 --> 00:07:21.640
1, 2, 3, 4.
135
00:07:21.640 --> 00:07:24.440
They're all different.
136
00:07:24.440 --> 00:07:29.960
The first thing you need to notice is that it's completely not coincidental.
137
00:07:29.960 --> 00:07:34.960
It doesn't matter whether the number was 6 and our prime was 5, so we did it four times.
138
00:07:34.960 --> 00:07:43.240
With any A and with any P, this sequence of numbers is going to give congruences mod
139
00:07:43.240 --> 00:07:46.120
P that are all distinct.
140
00:07:46.120 --> 00:07:49.200
Let's try to figure out why that's true.
141
00:07:49.200 --> 00:07:51.200
It doesn't necessarily start with 1, that's just a-
142
00:07:51.200 --> 00:07:56.000
It doesn't necessarily start with 1, but they're all be distinct.
143
00:07:56.000 --> 00:07:59.000
Now why is that?
144
00:07:59.000 --> 00:08:03.280
Take any two of these, any two at all.
145
00:08:03.280 --> 00:08:10.160
They differ by multiples of- what's the difference between them?
146
00:08:10.160 --> 00:08:11.160
Multiple of A, right?
147
00:08:11.160 --> 00:08:12.520
Two A and seven A.
148
00:08:12.520 --> 00:08:15.400
They differ by a multiple of A.
149
00:08:15.400 --> 00:08:20.960
What I'm going to convince you is that if I take any two of these, and I look at their
150
00:08:20.960 --> 00:08:27.880
difference, that that difference will never be a multiple of P. If they're going to have
151
00:08:27.880 --> 00:08:31.400
the same congruence with respect to P, then the difference between them would have to be
152
00:08:31.400 --> 00:08:36.720
a multiple of P. If they're both congruent to 1, then the difference between them would
153
00:08:36.720 --> 00:08:38.520
be a multiple of 5.
154
00:08:38.520 --> 00:08:42.600
I'm going to convince you that the difference between any two is never a multiple of P.
155
00:08:42.600 --> 00:08:46.800
The difference between any two of these would never be a multiple of 5.
156
00:08:46.800 --> 00:08:51.840
Therefore they have to be congruent to different numbers with respect to 5.
157
00:08:51.840 --> 00:09:00.640
How do you know that any multiple of A, seven A, six A, up to P minus 1 A?
158
00:09:00.640 --> 00:09:04.000
How do you know that none of them are going to get divisible by P?
159
00:09:04.000 --> 00:09:16.960
Well, that A could have a factor of P in it.
160
00:09:16.960 --> 00:09:19.960
No, that would say A was not a single of my team.
161
00:09:19.960 --> 00:09:22.360
Oh, well that was lucky.
162
00:09:22.360 --> 00:09:24.880
Right, right, right, you're both right.
163
00:09:24.880 --> 00:09:30.760
P can never divide into A because that was our main assumption.
164
00:09:30.760 --> 00:09:33.160
Without that assumption, this doesn't work.
165
00:09:33.160 --> 00:09:39.200
So P will never divide into A. Why can't P divide into, say the difference is like eight
166
00:09:39.200 --> 00:09:41.840
times A. It won't go into A. We know that.
167
00:09:41.840 --> 00:09:44.440
But maybe we'll go into the eight.
168
00:09:44.440 --> 00:09:47.480
We'll get all these numbers that could be the differences between these guys.
169
00:09:47.480 --> 00:09:48.480
Right?
170
00:09:48.480 --> 00:09:51.280
They're going to be either 1, 2, 3, all the way up to P minus 1.
171
00:09:51.280 --> 00:09:55.120
P can't go into something less than itself.
172
00:09:55.120 --> 00:10:00.000
So there's no way if you take any pair of these and you subtract it that their difference
173
00:10:00.000 --> 00:10:01.760
is going to be divisible by P.
174
00:10:01.760 --> 00:10:06.360
There's no way you could take any pair of these and subtract them and expect the difference
175
00:10:06.360 --> 00:10:08.520
to be divisible by 5.
176
00:10:08.520 --> 00:10:10.120
The difference between these two is 12.
177
00:10:10.120 --> 00:10:11.680
The difference between these two is 12.
178
00:10:11.680 --> 00:10:13.880
Between these two is 18.
179
00:10:13.880 --> 00:10:16.440
The differences are none of them are divisible by 5.
180
00:10:16.440 --> 00:10:19.480
Therefore, no pair could have the same congruence with respect to 5.
181
00:10:19.480 --> 00:10:20.480
Yeah.
182
00:10:20.480 --> 00:10:25.960
Is that because no single one of them is even divisible by 5?
183
00:10:25.960 --> 00:10:28.800
Is that the first thing that you put?
184
00:10:28.800 --> 00:10:34.240
I didn't show that, but it's true that no single one of them is divisible by 5.
185
00:10:34.240 --> 00:10:39.360
So you showed how the coefficients are basically can't be divisible by 5 because they're
186
00:10:39.360 --> 00:10:40.360
less than that.
187
00:10:40.360 --> 00:10:42.960
And the A can't be divisible by 5.
188
00:10:42.960 --> 00:10:43.960
You're 100% right.
189
00:10:43.960 --> 00:10:47.280
I've also showed, although I didn't mention it explicitly, that none of these could be
190
00:10:47.280 --> 00:10:52.840
divisible by P and no difference between any two could be divisible by P.
191
00:10:52.840 --> 00:10:56.480
The difference between any pair is very important because that shows that the congruence
192
00:10:56.480 --> 00:11:00.720
with respect to P of this one and the congruence with respect to P of this one are going to
193
00:11:00.720 --> 00:11:01.720
be different.
194
00:11:01.720 --> 00:11:05.320
If they were the same, then the difference between them would be a multiple of P. And the
195
00:11:05.320 --> 00:11:09.280
difference between them can't be a multiple of P. That's what we've discussed.
196
00:11:09.280 --> 00:11:11.840
How is it that the difference can't be?
197
00:11:11.840 --> 00:11:16.040
Because the difference between any pair here has to be some multiple of A.
198
00:11:16.040 --> 00:11:18.240
Oh, right.
199
00:11:18.240 --> 00:11:22.360
And it's got to be some multiple of A that's less than P minus 1, multiples.
200
00:11:22.360 --> 00:11:24.360
So for the same reason that it's individual.
201
00:11:24.360 --> 00:11:27.680
The same reason that any individual one can't be divisible by P. That's the same reason
202
00:11:27.680 --> 00:11:30.680
that the difference between any two can't be divisible by P. Because the difference between
203
00:11:30.680 --> 00:11:34.520
any two is the same as one of these individual.
204
00:11:34.520 --> 00:11:36.440
Yeah, tone.
205
00:11:36.440 --> 00:11:38.480
Okay.
206
00:11:38.480 --> 00:11:39.480
Questions.
207
00:11:39.480 --> 00:11:40.480
All right.
208
00:11:40.480 --> 00:11:41.480
So what does this mean?
209
00:11:41.480 --> 00:11:43.480
It means the following.
210
00:11:43.480 --> 00:11:47.920
That somehow, if I figured out the congruences of all these numbers with respect to P and I
211
00:11:47.920 --> 00:11:50.240
wrote them down, I'd have all the numbers.
212
00:11:50.240 --> 00:11:52.320
How many congruences do you have with respect to P?
213
00:11:52.320 --> 00:11:57.760
You can have 1, you can have 2, 3, 4, all the way up to P minus 1.
214
00:11:57.760 --> 00:11:59.040
We're not going to get 0 here, right?
215
00:11:59.040 --> 00:12:02.840
It's not ever divisible by P. Now, they could be in any order we want.
216
00:12:02.840 --> 00:12:05.800
So we have to come up with an argument here that doesn't use any order.
217
00:12:05.800 --> 00:12:07.880
So here's our argument.
218
00:12:07.880 --> 00:12:11.120
So I didn't write this down, but you should have in your notes every one of these has to
219
00:12:11.120 --> 00:12:13.720
have a different congruence with respect to P. Okay.
220
00:12:13.720 --> 00:12:15.240
Make that note to yourselves.
221
00:12:15.240 --> 00:12:17.240
And here's what we say then.
222
00:12:17.240 --> 00:12:29.880
So hence, I'm going to multiply all these things together.
223
00:12:29.880 --> 00:12:31.960
And I'm going to make a congruence equation.
224
00:12:31.960 --> 00:12:36.520
If this one and this one and this one and this one all together come up with all the
225
00:12:36.520 --> 00:12:40.240
congruences from 1 to P minus 1, I don't know what order they are.
226
00:12:40.240 --> 00:12:44.720
So if I multiply them all together, I know that they're going to equal to the product
227
00:12:44.720 --> 00:12:45.720
of all those congruences.
228
00:12:45.720 --> 00:12:47.200
I just don't know what order.
229
00:12:47.200 --> 00:12:49.680
If I'm multiplying, I don't really care about the order.
230
00:12:49.680 --> 00:13:07.640
So this is going to be 1 times 2 times 3 all the way up to P minus 1, mod P.
231
00:13:07.640 --> 00:13:10.240
There's A's here, but there's no A's here.
232
00:13:10.240 --> 00:13:11.240
What happened to it?
233
00:13:11.240 --> 00:13:16.600
Because I know that each of these individually is going to be congruent to one of these numbers,
234
00:13:16.600 --> 00:13:18.400
1, 2, 3, up to P minus 1.
235
00:13:18.400 --> 00:13:23.800
And each of them is going to be congruent to a different one.
236
00:13:23.800 --> 00:13:29.440
So if I multiply these all together and I check their congruence with respect to P,
237
00:13:29.440 --> 00:13:33.680
it's going to be equal to the product of all the congruences together.
238
00:13:33.680 --> 00:13:35.200
I just don't know what order.
239
00:13:35.200 --> 00:13:40.280
So I might as well just write it in ascending order.
240
00:13:40.280 --> 00:13:41.280
Okay.
241
00:13:41.280 --> 00:13:44.040
Are we positive that we're not going to skip any?
242
00:13:44.040 --> 00:13:48.400
Yeah, because we know they all have to be different and there's P minus 1 of them.
243
00:13:48.400 --> 00:13:50.080
So we've got to have one of each.
244
00:13:50.080 --> 00:13:51.240
And that's the right question to ask.
245
00:13:51.240 --> 00:13:54.280
That's what makes this argument so clever.
246
00:13:54.280 --> 00:13:56.000
We've shown that there can't be duplicates.
247
00:13:56.000 --> 00:13:58.200
We know we have to get P minus 1 of them.
248
00:13:58.200 --> 00:14:01.560
So the only choices are 1 all the way up through P minus 1.
249
00:14:01.560 --> 00:14:03.280
All right, so let's check to make sure this works.
250
00:14:03.280 --> 00:14:06.120
Okay, so what would this mean in the example that we just did?
251
00:14:06.120 --> 00:14:15.480
It would mean that 6 times 12 times 18 times 24 is congruent to 1 times 2 times 3 times 4
252
00:14:15.480 --> 00:14:16.480
mod 5.
253
00:14:16.480 --> 00:14:21.880
That better be true.
254
00:14:21.880 --> 00:14:26.280
Well we know that 6 is congruent to 1 and 12 is congruent to 2 and 18 is congruent to 3
255
00:14:26.280 --> 00:14:28.160
and 24 is congruent to 4.
256
00:14:28.160 --> 00:14:33.040
So this should work and you can multiply it out and check.
257
00:14:33.040 --> 00:14:35.960
When you multiply these all together, you get all terms that have
258
00:14:35.960 --> 00:14:39.840
multiples of 5's in them except for the only term that doesn't necessarily have a
259
00:14:39.840 --> 00:14:43.960
multiple of 5 is 1 times 2 times 3 times 4.
260
00:14:43.960 --> 00:14:47.760
All the other terms have multiples of 5's in them.
261
00:14:47.760 --> 00:14:49.800
That's another way to look at it.
262
00:14:49.800 --> 00:14:51.960
Okay, yeah, Theresa?
263
00:14:51.960 --> 00:14:55.800
One says that you're showing the line of the common factor.
264
00:14:55.800 --> 00:14:59.600
It doesn't mean anything to me at this moment.
265
00:14:59.600 --> 00:15:06.600
These two are the same because if we don't care about multiples of 5, they're equal.
266
00:15:06.600 --> 00:15:09.600
But it's going to overall what is congruent?
267
00:15:09.600 --> 00:15:16.600
It seems to me from what I think so far that has to do with factoring out a common factor.
268
00:15:16.600 --> 00:15:20.400
Yeah, this is what congruent means.
269
00:15:20.400 --> 00:15:26.000
7 and 2 are congruent mod 5 because they differ by a multiple of 5.
270
00:15:26.000 --> 00:15:28.600
12 and 2 are.
271
00:15:28.600 --> 00:15:35.600
12 and 2 are congruent mod 5.
272
00:15:35.600 --> 00:15:40.960
Okay, it's a way of saying that it's a way of actually setting up an equivalence
273
00:15:40.960 --> 00:15:43.240
relation on all the numbers in the world.
274
00:15:43.240 --> 00:15:49.120
2 and 7 and 12 and 17 and 22 are all in the same equivalence relation.
275
00:15:49.120 --> 00:15:50.680
They're all the same.
276
00:15:50.680 --> 00:15:54.240
Anything that differ by 5 are all the same.
277
00:15:54.240 --> 00:15:55.600
Right.
278
00:15:55.600 --> 00:16:00.600
So, what I'm saying is that none of these are the same with respect to P.
279
00:16:00.600 --> 00:16:02.600
They're all different.
280
00:16:02.600 --> 00:16:04.600
Does that make sense?
281
00:16:04.600 --> 00:16:05.600
Yeah.
282
00:16:05.600 --> 00:16:06.600
Joe, what's your...
283
00:16:06.600 --> 00:16:11.600
No, I don't understand how those two are 7 and 12 both congruent and 2 are not that.
284
00:16:11.600 --> 00:16:13.600
That's what the definition means.
285
00:16:13.600 --> 00:16:18.600
What this means is that you subtract 2 from 7 and you see if it's the visible by 5.
286
00:16:18.600 --> 00:16:22.600
Check the difference of the 2 and see if they're divisible by 5.
287
00:16:22.600 --> 00:16:25.600
Okay.
288
00:16:25.600 --> 00:16:28.600
Yeah, do you mean...
289
00:16:28.600 --> 00:16:29.600
They both are the same remainder.
290
00:16:29.600 --> 00:16:30.600
Right.
291
00:16:30.600 --> 00:16:32.600
So, all the numbers in the world are in 5 classes.
292
00:16:32.600 --> 00:16:40.600
Either they're divisible by 5 or they have a remainder of 1 or they have a remainder of 2 or they have a remainder of 3 or they have a remainder of 4.
293
00:16:40.600 --> 00:16:50.600
Every single number is in one of those equivalence classes and you can prove that that relation of congruent is reflexive, symmetric and transitive.
294
00:16:50.600 --> 00:16:53.600
So, it's partitions all the integers into 1 of 5 groups.
295
00:16:53.600 --> 00:16:56.600
You're very familiar with one thing just like this.
296
00:16:56.600 --> 00:16:57.600
Just odd and even numbers.
297
00:16:57.600 --> 00:16:58.600
Right.
298
00:16:58.600 --> 00:17:04.600
Odd and even numbers are just numbers that are congruent mod 2. Right.
299
00:17:04.600 --> 00:17:05.600
Okay.
300
00:17:05.600 --> 00:17:08.600
So, there's two equivalence classes. They're the odd numbers and the even numbers.
301
00:17:08.600 --> 00:17:09.600
Yeah.
302
00:17:09.600 --> 00:17:15.600
For a common number one, you can put mod on one side and it applies to the whole thing.
303
00:17:15.600 --> 00:17:20.600
And for an equation, you apply mod 2, whichever side you want to specify.
304
00:17:20.600 --> 00:17:22.600
The reason I'm asking you...
305
00:17:22.600 --> 00:17:23.600
Yeah.
306
00:17:23.600 --> 00:17:24.600
Okay.
307
00:17:24.600 --> 00:17:25.600
That's a yes.
308
00:17:25.600 --> 00:17:28.600
No, I was saying, yeah, the reason you're asking is...
309
00:17:28.600 --> 00:17:30.600
The only reason you're asking is for clarity.
310
00:17:30.600 --> 00:17:33.600
I mean, I understand what's going on here perfectly.
311
00:17:33.600 --> 00:17:41.600
The only ever time you have mod p in parentheses is at the end of an equation to mean that this equality is only true...
312
00:17:41.600 --> 00:17:49.600
Modulo p, meaning it's only true if we don't care about differences that are multiples of p.
313
00:17:49.600 --> 00:17:53.600
But these two are the same if the remainder is the same when you divide by p.
314
00:17:53.600 --> 00:17:54.600
All those are...
315
00:17:54.600 --> 00:17:56.600
Please, mod p.
316
00:17:56.600 --> 00:18:01.600
Okay.
317
00:18:01.600 --> 00:18:05.600
No, I think that's the only place... that's the main place you would see it.
318
00:18:05.600 --> 00:18:06.600
Yeah.
319
00:18:06.600 --> 00:18:08.600
The main place you would see it.
320
00:18:08.600 --> 00:18:09.600
Yeah.
321
00:18:09.600 --> 00:18:12.600
I mean, I don't know.
322
00:18:12.600 --> 00:18:15.600
I mean, you probably might see it somewhere else, but...
323
00:18:15.600 --> 00:18:18.600
I have like two equals seven mod five.
324
00:18:18.600 --> 00:18:19.600
Yeah, but that's...
325
00:18:19.600 --> 00:18:21.600
Mod five just refers to the...
326
00:18:21.600 --> 00:18:24.600
Yeah, you'd see it like this, but that's the same as that.
327
00:18:24.600 --> 00:18:25.600
Two equals seven.
328
00:18:25.600 --> 00:18:27.600
Two equals seven mod five.
329
00:18:27.600 --> 00:18:29.600
You ever see it as an operator?
330
00:18:29.600 --> 00:18:30.600
Like, friends.
331
00:18:30.600 --> 00:18:33.600
Oh, and a computer program, you might see it as an operator.
332
00:18:33.600 --> 00:18:34.600
Right.
333
00:18:34.600 --> 00:18:36.600
You'd see it like this in a computer program.
334
00:18:36.600 --> 00:18:39.600
Seven mod two.
335
00:18:39.600 --> 00:18:42.600
That doesn't completely different meaning.
336
00:18:42.600 --> 00:18:45.600
But you would never use that five equals two.
337
00:18:45.600 --> 00:18:47.600
Seven mod two equals one.
338
00:18:47.600 --> 00:18:49.600
Seven mod five equals two.
339
00:18:49.600 --> 00:18:50.600
Right.
340
00:18:50.600 --> 00:18:54.600
Seven mod two, it means what is the remainder of seven when you divide two into it?
341
00:18:54.600 --> 00:18:57.600
You would use it mathematically.
342
00:18:57.600 --> 00:19:00.600
No, not unless it was a computer program.
343
00:19:00.600 --> 00:19:04.600
I wouldn't use it like a multiple... like a real multiple symbol.
344
00:19:04.600 --> 00:19:06.600
Well, you wouldn't use the word mod.
345
00:19:06.600 --> 00:19:07.600
No.
346
00:19:07.600 --> 00:19:09.600
You'd see it, see it like this.
347
00:19:09.600 --> 00:19:10.600
Right.
348
00:19:10.600 --> 00:19:11.600
It's a percent sign, right?
349
00:19:11.600 --> 00:19:13.600
And in Pascal, they actually called it the word mod.
350
00:19:13.600 --> 00:19:18.600
But outside of the language Pascal, I don't think people generally use the word mod as an operator.
351
00:19:18.600 --> 00:19:21.600
But you wouldn't use it in algebra.
352
00:19:21.600 --> 00:19:22.600
Generally not.
353
00:19:22.600 --> 00:19:23.600
Right.
354
00:19:25.600 --> 00:19:28.600
Well, if you did, you'd have a different symbol for it.
355
00:19:28.600 --> 00:19:31.600
I mean, you often talk about the remainders of things.
356
00:19:31.600 --> 00:19:36.600
It's like it would be useful when stating an algorithm like this to be a...
357
00:19:36.600 --> 00:19:40.600
You could use the word mod, you could use percent, you could use...
358
00:19:40.600 --> 00:19:44.600
You could use the greatest... you could use the upper ceiling...
359
00:19:44.600 --> 00:19:47.600
There's a lot of ways to describe mod.
360
00:19:47.600 --> 00:19:51.600
It's basically a division where you subtract the whole number part away.
361
00:19:51.600 --> 00:19:53.600
So there's lots of ways to do it.
362
00:19:53.600 --> 00:19:55.600
That one's ceiling mean.
363
00:19:55.600 --> 00:19:57.600
Sealing means round up.
364
00:19:57.600 --> 00:19:58.600
Oh, okay.
365
00:19:58.600 --> 00:20:04.600
So if you divide and then round down and then subtract, you get mod.
366
00:20:07.600 --> 00:20:08.600
All right.
367
00:20:08.600 --> 00:20:10.600
Are we back on track?
368
00:20:10.600 --> 00:20:12.600
Other questions?
369
00:20:14.600 --> 00:20:16.600
All right. So here's where we're up to.
370
00:20:16.600 --> 00:20:19.600
We take these numbers, we multiply them through them presumably.
371
00:20:19.600 --> 00:20:22.600
24 mod 5 is going to be what?
372
00:20:22.600 --> 00:20:24.600
4.
373
00:20:24.600 --> 00:20:25.600
4.
374
00:20:25.600 --> 00:20:30.600
And then, presumably, if we multiply these all together, we'll get a remainder 4 and you will.
375
00:20:30.600 --> 00:20:32.600
And this is true.
376
00:20:32.600 --> 00:20:34.600
So where do we go from here?
377
00:20:34.600 --> 00:20:37.600
We're actually not too far here from here.
378
00:20:37.600 --> 00:20:39.600
We can actually get there in a couple of steps.
379
00:20:39.600 --> 00:20:41.600
And then the proof is going to be done.
380
00:20:41.600 --> 00:20:44.600
So the main logic in this proof is going from here to here.
381
00:20:44.600 --> 00:20:46.600
In writing it down, I'm going to regroup here a little bit.
382
00:20:46.600 --> 00:20:49.600
How many a's do I have?
383
00:20:49.600 --> 00:20:50.600
P minus 1a.
384
00:20:50.600 --> 00:20:53.600
So I've got a to the p minus 1.
385
00:20:53.600 --> 00:20:56.600
Times what?
386
00:20:56.600 --> 00:21:00.600
Good. Times p minus 1 factorial.
387
00:21:00.600 --> 00:21:06.600
Good. I got p minus 1a's and I got 1, 2, 3, 4 all the way up to p minus 1.
388
00:21:06.600 --> 00:21:08.600
That's this side.
389
00:21:08.600 --> 00:21:12.600
And I'll subtract the other side off. What do I get down the other side?
390
00:21:12.600 --> 00:21:14.600
P minus 1 factorial.
391
00:21:14.600 --> 00:21:17.600
This is the difference between the left and the right side.
392
00:21:17.600 --> 00:21:22.600
And if there are congruent mod p, it means and we write it like this and
393
00:21:22.600 --> 00:21:27.600
this means that p divides this equally evenly.
394
00:21:27.600 --> 00:21:30.600
So this implies this.
395
00:21:30.600 --> 00:21:37.600
This means that p divides the difference between these two.
396
00:21:37.600 --> 00:21:45.600
And they're different by a factor of p because they work out to the same
397
00:21:45.600 --> 00:21:47.600
their growth bond for.
398
00:21:47.600 --> 00:21:52.600
So we write because they're both congruent to 4 mod 5.
399
00:21:52.600 --> 00:21:57.600
So when you subtract them from each other, there's going to be a multiple of 5
400
00:21:57.600 --> 00:22:00.600
between them.
401
00:22:00.600 --> 00:22:05.600
So things that are congruent to 4 mod 5 would be 4, 9, 14, etc.
402
00:22:05.600 --> 00:22:09.600
So if you subtract any two of them, you get a multiple of 5.
403
00:22:09.600 --> 00:22:13.600
Or in this case, a multiple of p.
404
00:22:13.600 --> 00:22:20.600
And you just say that the left side is that a to the p minus 1 power of 1 is p minus 1 factorial.
405
00:22:20.600 --> 00:22:23.600
The common p minus 1 factorial.
406
00:22:23.600 --> 00:22:28.600
Therefore, a to the p minus 1 is the common p minus 1.
407
00:22:28.600 --> 00:22:31.600
I could do that.
408
00:22:31.600 --> 00:22:37.600
If you see that, fine, then no reason.
409
00:22:37.600 --> 00:22:40.600
That's fine. You get it completely.
410
00:22:40.600 --> 00:22:45.600
Well, I'm trying to break it up into smaller steps.
411
00:22:45.600 --> 00:22:48.600
This implies this, and we're trying to get to this.
412
00:22:48.600 --> 00:22:52.600
So we have one more step to get there.
413
00:22:52.600 --> 00:23:00.600
p divides p minus 1 factorial times a to the p minus 1.
414
00:23:00.600 --> 00:23:02.600
Did I do that right?
415
00:23:02.600 --> 00:23:03.600
No.
416
00:23:03.600 --> 00:23:06.600
Minus 1. There we go. That's what I'm looking for.
417
00:23:06.600 --> 00:23:09.600
I tackered out a p minus 1 factorial.
418
00:23:09.600 --> 00:23:15.600
So if p divides this, can p divide p minus 1 factorial?
419
00:23:15.600 --> 00:23:18.600
All the numbers here are smaller than p.
420
00:23:18.600 --> 00:23:21.600
There's no factor here that's as big as this prime number.
421
00:23:21.600 --> 00:23:25.600
So this prime number will never ever divide anything in here.
422
00:23:25.600 --> 00:23:30.600
So if it divides this product, and it can't divide the first part,
423
00:23:30.600 --> 00:23:36.600
therefore it has to divide the second part.
424
00:23:36.600 --> 00:23:42.600
It's like saying a 5 divides into 4 times 3 times 2 times 1 times something else.
425
00:23:42.600 --> 00:23:45.600
Well, it's not going to be able to divide into any of these,
426
00:23:45.600 --> 00:23:48.600
so it's got to be able to divide into this one.
427
00:23:48.600 --> 00:23:55.600
So this implies that p divides into a to the p minus 1 minus 1.
428
00:23:55.600 --> 00:23:58.600
And that's exactly what this says.
429
00:23:58.600 --> 00:24:04.600
That p divides into the difference between a to the p minus 1 and 1.
430
00:24:04.600 --> 00:24:07.600
So the main step in the proof is going from here to here,
431
00:24:07.600 --> 00:24:10.600
and then there's just a little algebra.
432
00:24:10.600 --> 00:24:14.600
Let me stop. This ends this contained part of the lecture today.
433
00:24:14.600 --> 00:24:16.600
So we're done with this proof.
434
00:24:16.600 --> 00:24:19.600
If you have questions on it, I'll stop now.
435
00:24:19.600 --> 00:24:22.600
If you don't get the proof, it's okay.
436
00:24:22.600 --> 00:24:25.600
Just understand what the proof says. Understand the result.
437
00:24:25.600 --> 00:24:28.600
And if you do get the proof, or you have some more questions,
438
00:24:28.600 --> 00:24:30.600
let me take them now. Yeah, Donna.
439
00:24:30.600 --> 00:24:33.600
Can you maybe explain what p has to be a prime number for this to be true?
440
00:24:33.600 --> 00:24:36.600
That's a good question. Whenever those conditions, you kind of want to make sure
441
00:24:36.600 --> 00:24:39.600
that they're necessary, right?
442
00:24:39.600 --> 00:24:42.600
Why does p have to be a prime number? Where did we use it in any step?
443
00:24:42.600 --> 00:24:45.600
It's like five steps. It doesn't divide.
444
00:24:45.600 --> 00:24:47.600
Any number is smaller than that.
445
00:24:47.600 --> 00:24:51.600
In this step here. Right. Baruch thinks it helps here.
446
00:24:51.600 --> 00:24:54.600
What do you think, Donna? What if this number wasn't five?
447
00:24:54.600 --> 00:24:58.600
What if this number was eight?
448
00:24:58.600 --> 00:25:00.600
That's not a prime number.
449
00:25:00.600 --> 00:25:03.600
Then I can't say it doesn't divide here.
450
00:25:03.600 --> 00:25:06.600
It could divide this because four times two gives you eight.
451
00:25:06.600 --> 00:25:12.600
But when it's prime, I know it's not going to be able to divide any possible combinations of these,
452
00:25:12.600 --> 00:25:16.600
because there's no way to split that number up into pieces,
453
00:25:16.600 --> 00:25:18.600
because it's a prime number.
454
00:25:18.600 --> 00:25:21.600
So it's used in this step from going here to here.
455
00:25:21.600 --> 00:25:24.600
And Gary, maybe that's the step that you kind of internalized in your head,
456
00:25:24.600 --> 00:25:26.600
but really needs a description.
457
00:25:26.600 --> 00:25:30.600
P divides the second part because p can't divide this part.
458
00:25:30.600 --> 00:25:33.600
And the reason it can't divide this part is because p is a prime number.
459
00:25:33.600 --> 00:25:37.600
Otherwise, you would get stuck here, and there'd be no guarantee that p divides this part.
460
00:25:37.600 --> 00:25:40.600
P might divide the whole thing only because it divides this first part.
461
00:25:40.600 --> 00:25:44.600
Do you get it, Donna? That's a very good question, and it's a very natural question to ask.
462
00:25:44.600 --> 00:25:46.600
Are there other questions?
463
00:25:46.600 --> 00:25:50.600
You're right down the alphabet, A, B, C, D, E, F, G, all the way up to x, y, z.
464
00:25:50.600 --> 00:25:54.600
And now, let's just shift up all the letters by some fixed amount.
465
00:25:54.600 --> 00:26:04.600
Say by three. So A is going to turn into D, and B will turn into E, F, G, and z would be C, and this would be B.
466
00:26:04.600 --> 00:26:08.600
Okay? I mean, kids do this. They get on cereal boxes, right?
467
00:26:08.600 --> 00:26:09.600
This kind of...
468
00:26:09.600 --> 00:26:12.600
In crem-magic decoders, right? Magic decoder rings, right?
469
00:26:12.600 --> 00:26:13.600
The same idea.
470
00:26:13.600 --> 00:26:15.600
Now, let's encode it a message just like this.
471
00:26:15.600 --> 00:26:20.600
You had no idea how I encoded it, but this is the way I actually did it.
472
00:26:20.600 --> 00:26:24.600
You know, so I have a whole message encoded this way. How would you decode it?
473
00:26:24.600 --> 00:26:26.600
Try out 26 combinations.
474
00:26:26.600 --> 00:26:29.600
Right, there's only 26 combinations. There's only 26 ways I could have done it.
475
00:26:29.600 --> 00:26:34.600
Try out 26. 25 of them will probably be gibberish, and one will be a message.
476
00:26:34.600 --> 00:26:40.600
And you're done. You could do this by hand in a few minutes.
477
00:26:40.600 --> 00:26:44.600
If you had a computer, you could do it in a couple of seconds.
478
00:26:44.600 --> 00:26:47.600
Right? It's not a hard thing to do.
479
00:26:47.600 --> 00:26:50.600
So, even in World War II, this is obviously not good enough.
480
00:26:50.600 --> 00:26:53.600
Even in ancient times, this isn't good enough. You need something a little better.
481
00:26:53.600 --> 00:26:59.600
So here's a way to make it much more complicated, or what seems to be more complicated at first glance.
482
00:26:59.600 --> 00:27:07.600
A way to make it more complicated is, let's call this the D encoding.
483
00:27:07.600 --> 00:27:10.600
Okay, because I start with D and move away.
484
00:27:10.600 --> 00:27:14.600
Okay, so now let's encode this way.
485
00:27:14.600 --> 00:27:19.600
I have a code word called dumbbell. How do you sell dumbbells to these?
486
00:27:19.600 --> 00:27:23.600
Yeah, dumbbell.
487
00:27:23.600 --> 00:27:26.600
Okay, here's the way I'm going to encode a message.
488
00:27:26.600 --> 00:27:30.600
Let's say I have a message. Hello.
489
00:27:30.600 --> 00:27:32.600
Here's how I would encode it.
490
00:27:32.600 --> 00:27:37.600
I would take the H and encode it using the D encoding scheme.
491
00:27:37.600 --> 00:27:41.600
So that would turn it into a...
492
00:27:41.600 --> 00:27:46.600
Okay, okay.
493
00:27:46.600 --> 00:27:47.600
Okay.
494
00:27:47.600 --> 00:27:51.600
And then I take the E and encode it using the U encoding scheme.
495
00:27:51.600 --> 00:27:53.600
Whatever that ends up being.
496
00:27:53.600 --> 00:27:56.600
And then I take the L and encode it using the M,
497
00:27:56.600 --> 00:28:00.600
and the other L encode it using a B, and the O using the other B.
498
00:28:00.600 --> 00:28:05.600
And if the message goes on and on and on, sooner or later I hit the end of my encoding word,
499
00:28:05.600 --> 00:28:08.600
and then I wrap around to the beginning.
500
00:28:08.600 --> 00:28:10.600
Everybody got the idea?
501
00:28:10.600 --> 00:28:13.600
It's much harder to decode.
502
00:28:13.600 --> 00:28:17.600
How many different possible things do you have to try,
503
00:28:17.600 --> 00:28:21.600
completely brute force to decode a message that was encoded like this?
504
00:28:21.600 --> 00:28:23.600
If you have no idea what the code word is.
505
00:28:23.600 --> 00:28:25.600
Do you know the length of the code word?
506
00:28:25.600 --> 00:28:27.600
If you don't know anything, you're really in trouble.
507
00:28:27.600 --> 00:28:31.600
So let's say you get a spy, and you figure out the length of the code word.
508
00:28:31.600 --> 00:28:33.600
Code word.
509
00:28:33.600 --> 00:28:36.600
26, 1, 2, 3, 4, 5, 6, 7.
510
00:28:36.600 --> 00:28:38.600
Right? We can all count.
511
00:28:38.600 --> 00:28:40.600
I can open it.
512
00:28:40.600 --> 00:28:42.600
That's a lot.
513
00:28:42.600 --> 00:28:47.600
When if you have a code word that's 35 symbols long,
514
00:28:47.600 --> 00:28:50.600
it's not so practical to do this anymore.
515
00:28:50.600 --> 00:28:54.600
Okay, because it gets to be 26 to the 30 something.
516
00:28:54.600 --> 00:28:57.600
Everybody get the idea of why this is better?
517
00:28:57.600 --> 00:29:01.600
This really just shoots it up an exponential in that.
518
00:29:01.600 --> 00:29:04.600
But this is exactly the kind of encoding the Germans use.
519
00:29:04.600 --> 00:29:06.600
Give or take.
520
00:29:06.600 --> 00:29:14.600
And it's exactly the kind of stuff that was routinely broken using a combination of computer help and a combination of ingenuity.
521
00:29:14.600 --> 00:29:22.600
So without getting too much into the details, how would you go ahead and try to solve something like this without just brute force trying them all?
522
00:29:22.600 --> 00:29:24.600
Rob, you have a...
523
00:29:24.600 --> 00:29:29.600
You can use algorithms to look for the most common letters.
524
00:29:29.600 --> 00:29:33.600
Patterns of commonality, even for a pattern like that.
525
00:29:33.600 --> 00:29:35.600
It's not the end of the algorithm.
526
00:29:35.600 --> 00:29:37.600
That is actually one of the main ways they do it.
527
00:29:37.600 --> 00:29:40.600
Maybe I should follow up a little bit and be specific about Rob's suggestion.
528
00:29:40.600 --> 00:29:42.600
Here's one method.
529
00:29:42.600 --> 00:29:48.600
Every language seems to have some frequency of how often the letters show up in typical messages.
530
00:29:48.600 --> 00:29:51.600
Everybody knows this if you watch Wheel of Fortune.
531
00:29:51.600 --> 00:29:53.600
RST or the letter?
532
00:29:53.600 --> 00:29:55.600
Right, and it's like...
533
00:29:55.600 --> 00:30:00.600
You know this because the Wheel of Fortune, when somebody gets up there, you know,
534
00:30:00.600 --> 00:30:05.600
and I don't know what I have to spend some money to buy a letter or something.
535
00:30:05.600 --> 00:30:08.600
So you get a letter and you guess, Z. Is there a Z?
536
00:30:08.600 --> 00:30:10.600
And it's just like the crowd groans.
537
00:30:10.600 --> 00:30:12.600
Get a clue, right? Z.
538
00:30:12.600 --> 00:30:14.600
No, no, no, I mean X. I mean Q.
539
00:30:14.600 --> 00:30:17.600
Everybody knows that some letters come in more frequently.
540
00:30:17.600 --> 00:30:19.600
And you can do this very scientifically.
541
00:30:19.600 --> 00:30:26.600
You can say in theater productions, the letters group in this way.
542
00:30:26.600 --> 00:30:29.600
In letters, one to another, the letters group this way.
543
00:30:29.600 --> 00:30:31.600
The percentages might be a little off.
544
00:30:31.600 --> 00:30:34.600
And certain types of ways of expressing yourself in a particular language,
545
00:30:34.600 --> 00:30:37.600
you get this many percentage of ease, this many percentages of F's,
546
00:30:37.600 --> 00:30:39.600
this many percentages of D's.
547
00:30:39.600 --> 00:30:43.600
You can do this and you can get people to calculate it for you.
548
00:30:43.600 --> 00:30:46.600
So how does that help? Here's how it helps.
549
00:30:46.600 --> 00:30:48.600
Let's go here to the H.
550
00:30:48.600 --> 00:30:51.600
The H was encoded using D. Right?
551
00:30:51.600 --> 00:30:56.600
Now let's move on. One, two, three, four, five, six, seven, eight.
552
00:30:56.600 --> 00:31:02.600
The eighth letter is also going to be encoded using D.
553
00:31:02.600 --> 00:31:05.600
So you take the message that you intercepted.
554
00:31:05.600 --> 00:31:11.600
You take the first, the eighth, the ninth, one, two, three, four, five, six, seven, eight, right.
555
00:31:11.600 --> 00:31:15.600
The first, the ninth, the 17th.
556
00:31:15.600 --> 00:31:19.600
You take a whole equivalence class of letters.
557
00:31:19.600 --> 00:31:22.600
First, 9, 17, 26, 35.
558
00:31:22.600 --> 00:31:23.600
You take all those letters.
559
00:31:23.600 --> 00:31:30.600
You put them in a big, big group and you look to see.
560
00:31:30.600 --> 00:31:36.600
You look to see what happens when you encode them on each of the 26 possible decodement,
561
00:31:36.600 --> 00:31:38.600
each of the 26 possible ways.
562
00:31:38.600 --> 00:31:44.600
Which one gives you a collection of letters most like the ones you expect to have in the language that you're decoding.
563
00:31:44.600 --> 00:31:47.600
Which one looks most like German?
564
00:31:47.600 --> 00:31:50.600
Now when you do this, you get a lot that might look like German.
565
00:31:50.600 --> 00:31:54.600
Maybe three or four of them look like German instead of all 26.
566
00:31:54.600 --> 00:32:00.600
So now instead of 26 chances here, we got it narrowed down to just three.
567
00:32:00.600 --> 00:32:06.600
And maybe here it turns out that one is really strikingly like German, the rest are not.
568
00:32:06.600 --> 00:32:08.600
So this goes down to one.
569
00:32:08.600 --> 00:32:14.600
Suddenly the 26 to the eighth goes way down to something that you could actually do with a machine or by hand.
570
00:32:14.600 --> 00:32:18.600
And that's more or less how they went ahead trying to break the codes.
571
00:32:18.600 --> 00:32:28.600
In a hit or miss kind of fashion, ad hoc hoping that by these percentage tricks they could get it down to a reasonable amount they could actually look at.
572
00:32:28.600 --> 00:32:34.600
I think they were supposed to switch the key very frequently.
573
00:32:34.600 --> 00:32:35.600
Right.
574
00:32:35.600 --> 00:32:41.600
But help them at some point that they either because of sloppiness or whatever started using the same one.
575
00:32:41.600 --> 00:32:47.600
They use the same key for extended period which gave them enough time to do that.
576
00:32:47.600 --> 00:32:48.600
You switch this key.
577
00:32:48.600 --> 00:32:51.600
Right. You need a lot of data to get good information.
578
00:32:51.600 --> 00:32:58.600
So if you keep the key for a long time, you're going to be dead because the people get enough data and be able to decode it.
579
00:32:58.600 --> 00:33:01.600
At the same time, the other thing you want to switch is the length.
580
00:33:01.600 --> 00:33:04.600
If we don't know the length of this keyword, we can't do this at all.
581
00:33:04.600 --> 00:33:06.600
We don't know what the equivalence classes are.
582
00:33:06.600 --> 00:33:13.600
We don't know that it's the first and the ninth and the and the 18th and the second and the 10th and the 19th.
583
00:33:13.600 --> 00:33:14.600
We don't know what to do.
584
00:33:14.600 --> 00:33:17.600
So getting the length is very important.
585
00:33:17.600 --> 00:33:20.600
Predicting the length of the next keyword is important.
586
00:33:20.600 --> 00:33:28.600
And that was then with a combination of espionage and all sorts of other tricks guessing the method they use to pick the length of the next keyword.
587
00:33:28.600 --> 00:33:32.600
I don't think the length of the keyword is that hard.
588
00:33:32.600 --> 00:33:39.600
I think what you do from the code book, which I have Michael's copy.
589
00:33:39.600 --> 00:33:44.600
But it goes through the whole history.
590
00:33:44.600 --> 00:33:52.600
But I think what they did figure out the length is we look for repeated combinations of letters because it's a good chance that it's going to be encoded.
591
00:33:52.600 --> 00:33:54.600
So maybe you'll get that's true.
592
00:33:54.600 --> 00:34:00.600
So you can make backward inferences as to what the length of the keyword is based on repeated letters.
593
00:34:00.600 --> 00:34:01.600
That's true.
594
00:34:01.600 --> 00:34:09.600
All of these encryption methods, at least theoretically with enough computing power, can be decoded if you guess well enough and you have some help.
595
00:34:09.600 --> 00:34:13.600
Certainly, if you have a good spy, you're completely dead.
596
00:34:13.600 --> 00:34:17.600
If you steal the code word, then decoding it is trivial.
597
00:34:17.600 --> 00:34:19.600
But you just go backwards.
598
00:34:19.600 --> 00:34:25.600
So the goal is to get an encoding scheme where you can publish the encoding scheme in the newspaper.
599
00:34:25.600 --> 00:34:34.600
So everyone knows how to encode the message. But even though you've published the encoding scheme in the newspaper, nobody can easily use that to go backwards.
600
00:34:34.600 --> 00:34:41.600
Now, it seems like that's impossible at first glance because if I publish the code word, everybody can go backwards.
601
00:34:41.600 --> 00:34:48.600
Okay, adding numbers, module 026, which is what we're doing with this alphabet code, is the same as subtracting numbers, module 06.
602
00:34:48.600 --> 00:34:49.600
There's no difference.
603
00:34:49.600 --> 00:34:52.600
It's the same arithmetic. It's just as easy.
604
00:34:52.600 --> 00:35:01.600
So we need to come up with a function that's different than adding numbers, module 0 and other number, because the inverse of that subtracting numbers, module 0 and other numbers, is too easy.
605
00:35:01.600 --> 00:35:05.600
We need to go up with a function whose inverse is hard.
606
00:35:05.600 --> 00:35:06.600
Okay?
607
00:35:06.600 --> 00:35:09.600
So squaring numbers, the inverse is square rooting numbers.
608
00:35:09.600 --> 00:35:11.600
Whatever you can do forward, it seems you can do backwards.
609
00:35:11.600 --> 00:35:14.600
So we need to come up with an example that you can't do easily backwards.
610
00:35:14.600 --> 00:35:18.600
And that's what is done today.
611
00:35:18.600 --> 00:35:27.600
You publish the public way of encoding, anybody can encode it, but just because that's published doesn't mean anybody can decode it.
612
00:35:27.600 --> 00:35:29.600
Everybody is stuck for decoding it.
613
00:35:29.600 --> 00:35:39.600
So everybody can encode something, hand it to the person next to them, and ask them what was this when it started, and none of the people would know, even though they had just encoded something themselves.
614
00:35:39.600 --> 00:35:42.600
Alright, that's the idea. We're going to show how this works.
615
00:35:42.600 --> 00:35:43.600
All the details.
616
00:35:43.600 --> 00:35:46.600
I mean, no, nothing will be left out.
617
00:35:46.600 --> 00:35:48.600
There are questions about this.
618
00:35:48.600 --> 00:35:50.600
Alright, so how do you use something like this?
619
00:35:50.600 --> 00:35:54.600
If you have something like this, then you can buy stuff on the internet, even if you're a paranoid lunatic.
620
00:35:54.600 --> 00:35:55.600
It doesn't matter.
621
00:35:55.600 --> 00:36:04.600
You can think that the whole world is wanting to steal your credit card, and you would never, ever, like, leave a carbon in the old days, like in a garbage can.
622
00:36:04.600 --> 00:36:05.600
You'd rip it into shreds.
623
00:36:05.600 --> 00:36:08.600
If you're a person like that, you're completely safe.
624
00:36:08.600 --> 00:36:18.600
Because you encode your credit card with a publicly printed algorithm, and you send it over the internet, and nobody can decode it.
625
00:36:18.600 --> 00:36:20.600
Well, somebody's got to decode it, right?
626
00:36:20.600 --> 00:36:24.600
So there is a way to decode it, but you need special information.
627
00:36:24.600 --> 00:36:25.600
That information is secret.
628
00:36:25.600 --> 00:36:28.600
That information is in the hands of one particular person.
629
00:36:28.600 --> 00:36:31.600
So say you have a company, and they want to take orders by credit card.
630
00:36:31.600 --> 00:36:38.600
They hold the secret piece of information that helps them do the inverse, the decoding, in a vault.
631
00:36:38.600 --> 00:36:43.600
They use that to decode, and they publish in the newspaper the way you encode it.
632
00:36:43.600 --> 00:36:48.600
So everybody can send them their credit cards, and only they can figure out what the credit card numbers really are.
633
00:36:48.600 --> 00:36:51.600
So suddenly you can buy security.
634
00:36:51.600 --> 00:36:52.600
Right.
635
00:36:52.600 --> 00:36:56.600
Another way that this is used is a way that doesn't seem obvious at first.
636
00:36:56.600 --> 00:36:59.600
I'm not going to show you how to do it yet, but I'll show you another way to use it.
637
00:36:59.600 --> 00:37:01.600
What if I don't want to just send secure information?
638
00:37:01.600 --> 00:37:06.600
What if I want to send something to Chris, and it's not particularly secure?
639
00:37:06.600 --> 00:37:12.600
I don't really care if anybody sees it, but I want him to know that it's from me.
640
00:37:12.600 --> 00:37:13.600
Okay.
641
00:37:13.600 --> 00:37:18.600
He sent, say he wanted a vacation, and he sent in a problem set, and he wants to know whether I got it.
642
00:37:18.600 --> 00:37:21.600
So I want to send a message that says, yes, I got your problem set.
643
00:37:21.600 --> 00:37:25.600
I don't give a who to if anybody sees that message, but I want him to know that that message came from me,
644
00:37:25.600 --> 00:37:30.600
and that nobody just forged it, and you know wants them to think that his problem set got there.
645
00:37:30.600 --> 00:37:32.600
You can imagine this is very important, right?
646
00:37:32.600 --> 00:37:35.600
I mean, this is for signatures.
647
00:37:35.600 --> 00:37:37.600
I want to close a real estate deal, right?
648
00:37:37.600 --> 00:37:44.600
And nobody really cares about the details of the deal, but you want to know that I signed it, that I saw this deal, and I said, okay.
649
00:37:44.600 --> 00:37:45.600
You're on the other end.
650
00:37:45.600 --> 00:37:47.600
You want to verify that it came from me.
651
00:37:47.600 --> 00:37:48.600
So how do you do that?
652
00:37:48.600 --> 00:37:52.600
You can do that with the same scheme, even though it doesn't seem like you can.
653
00:37:52.600 --> 00:37:55.600
So here's the trick.
654
00:37:55.600 --> 00:38:06.600
We have this public encoding that anybody can do, and we have this private decoding.
655
00:38:06.600 --> 00:38:13.600
So here's how I can send a message to Chris, and make sure that it's that it works.
656
00:38:13.600 --> 00:38:17.600
I publish a public encoding out on the world.
657
00:38:17.600 --> 00:38:18.600
Anybody can see it.
658
00:38:18.600 --> 00:38:19.600
It's on a web page somewhere.
659
00:38:19.600 --> 00:38:21.600
And I keep the private thing for me.
660
00:38:21.600 --> 00:38:28.600
And I take my name, Shy Simonson, and I decode my name with my private code.
661
00:38:28.600 --> 00:38:35.600
I turn it into something else, some encrypted ugly thing that it came from.
662
00:38:35.600 --> 00:38:42.600
And then I send that privately decoded name over the internet at the end of my message.
663
00:38:42.600 --> 00:38:45.600
And Chris sees it, and it looks like gibberish.
664
00:38:45.600 --> 00:38:49.600
And he runs the public encoding program to encode it to see what it turns out to be.
665
00:38:49.600 --> 00:38:53.600
And if it turns out to be Shy Simonson, then he knows it's for me.
666
00:38:53.600 --> 00:38:54.600
How come?
667
00:38:54.600 --> 00:39:02.600
Because nobody could conceivably come up with the decoded version of my name because they don't have the private information.
668
00:39:02.600 --> 00:39:08.600
Nobody could figure out what Shy Simonson would look like if it got backward decoded.
669
00:39:08.600 --> 00:39:10.600
So I can guarantee that it was me.
670
00:39:10.600 --> 00:39:18.600
Now the thing is, if I routinely do this, and I just use my name, it gives people an infinite amount of time to sooner or later figure out what this is.
671
00:39:18.600 --> 00:39:21.600
And maybe they could figure out my private information or steal it somehow.
672
00:39:21.600 --> 00:39:28.600
And then they'll know that my name decodes back to this particular XYZQ, and they'll send XYZQ to anybody, and they'll forge my name.
673
00:39:28.600 --> 00:39:38.600
So the way this is actually done in practice is instead of using your name to decode, you send a message, some arbitrary message, and you make up some public function about that message.
674
00:39:38.600 --> 00:39:44.600
Like count the number of E's in this message, and you turn that into a number.
675
00:39:44.600 --> 00:39:49.600
And then you decode that number and send it to Chris.
676
00:39:49.600 --> 00:39:53.600
Chris can count the number of E's in the message. He knows how many there should be.
677
00:39:53.600 --> 00:40:01.600
He encodes that number I sent him, and if the encoding matches the actual number of E's in the message, then he knows that it came from me.
678
00:40:01.600 --> 00:40:09.600
Because I'm the only one who would know how to take that number of E's and send it back to the originally encoded message.
679
00:40:09.600 --> 00:40:16.600
He had a row here.
680
00:40:16.600 --> 00:40:24.600
Well, but if he had intercepted the message, he could only intercept my message and impersonate me for this particular message.
681
00:40:24.600 --> 00:40:42.600
Oh, and steal the right. Just send it. But that's true. But if I did it this last way, I just described. He could only intercept my message and impersonate me for this particular message.
682
00:40:42.600 --> 00:40:48.600
He could send any message with that number of E's in it if he knew that it was specifically the number of E's.
683
00:40:48.600 --> 00:40:57.600
That's a public. That information's public so that Chris can use it and write. He could send any number of E's in it.
684
00:40:57.600 --> 00:41:08.600
But the idea is that that particular function I talked about, you know, the number of E's. It's typically some hash function that that means it takes this big message and turns it into some number.
685
00:41:08.600 --> 00:41:12.600
And say we change it every week.
686
00:41:12.600 --> 00:41:19.600
Yeah, hash function is only like go to 128 bit numbers. So there's a number for every item in the universe coming from.
687
00:41:19.600 --> 00:41:26.600
Right. If it could go to a lot of different possibilities, his computer calculates which possibility ended up being.
688
00:41:26.600 --> 00:41:34.600
I do a two, but I decoded. And he's the only one who can check that it came from me. Well, everybody can check that it came from me.
689
00:41:34.600 --> 00:41:39.600
But I'm the only one who could have decoded it to begin with. So everybody get this idea. This idea is a little tricky.
690
00:41:39.600 --> 00:41:51.600
You can do both these ideas. If I have my own public private scheme and somebody else has their public private scheme, I can use their scheme to encode a message.
691
00:41:51.600 --> 00:41:56.600
I can use Chris's scheme to encode a message publicly and send it to him. He's the only one who'll be able to decode it.
692
00:41:56.600 --> 00:42:08.600
I use my private scheme to decode my signature or hash function on the message. When he gets it, he uses his, he uses my public encoding to encode my name.
693
00:42:08.600 --> 00:42:16.600
To see if it's the same as a hash function. And he uses his private decoding to decode the message that I encrypt it.
694
00:42:16.600 --> 00:42:23.600
So you can send messages securely and you can have the name or signature be completely verifiable.
695
00:42:23.600 --> 00:42:30.600
This version is going to be possible if you have the public information to figure out the private information.
696
00:42:30.600 --> 00:42:36.600
Then I'm just going to turn the dial up a little bit and that version is not going to be easy to get the private information.
697
00:42:36.600 --> 00:42:43.600
So I'm going to get you started on an easier example where you could figure out the private information if you had the public information.
698
00:42:43.600 --> 00:42:51.600
Where you could decode if you knew how to encode. And then I'm going to show you how to just turn it up a little bit and the decoding stuff gets too hard.
699
00:42:51.600 --> 00:42:56.600
It requires factoring really big numbers. Okay, questions so far?
700
00:42:56.600 --> 00:43:06.600
So here's how we're going to do it. In these examples, we're imagining that our messages are all converted into numbers. And the numbers are then converted into other numbers.
701
00:43:06.600 --> 00:43:10.600
So we send everything as numbers. It just makes it easier to present the whole idea.
702
00:43:10.600 --> 00:43:22.600
So if you have a message of characters, convert all those characters to numbers in some particular way, run it through your encoding scheme, send the new numbers to somebody else, they convert them back to the numbers you sent and then convert them into letters.
703
00:43:22.600 --> 00:43:31.600
So here's how it's done. You start by picking a prime number, any number at all. Let's say 17.
704
00:43:31.600 --> 00:43:47.600
And then you pick another number. Shoes, let's call it E. Such that the greatest common divisor of E and 16 is 1.
705
00:43:47.600 --> 00:44:00.600
Right, I don't mean 2.71828, right? E for encoding. Choose an E such that the greatest common divisor of E and 1 less than this number, the 16 is P minus 1.
706
00:44:00.600 --> 00:44:08.600
I'm doing a specific example, but you could do it in general with any prime number. Choose a number E such that the greatest common divisor of E and 16 is 1.
707
00:44:08.600 --> 00:44:22.600
So I'm going to pick E equals 5. EG, for example, E equals 5. This isn't too involved. So don't expect too much more. It's actually almost here.
708
00:44:22.600 --> 00:44:35.600
This information, the 5 and the 17, this is the public information. This gets published in the newspaper on the web.
709
00:44:35.600 --> 00:44:43.600
Some place where anybody can get to it. That's the information we need to do encoding. And I'm going to show you how you do encoding now.
710
00:44:43.600 --> 00:44:58.600
So let's say I want to encode some number. Let's say 6. You take 6. You raise it to the 5th power to the E power.
711
00:44:58.600 --> 00:45:11.600
Now this is what Tony's asking before. The answer is yes to your question. Do you ever use mod as an operator? You do. 6 to the 5th mod 17 means what's the remainder of 6 to the 5th with respect to 17?
712
00:45:11.600 --> 00:45:25.600
Yeah, yeah. Well, here's a straightforward answer. Finally, I understand what you're asking. 6 to the 5th mod 17. That means take 6 to the 5th, divide it by 17, and tell me what the remainder is.
713
00:45:25.600 --> 00:45:50.600
Anybody know what that is? I know what it is. What is it? Yeah, that's between 0 and 16. So what is it? It's 7. You get a computer to do it for you.
714
00:45:50.600 --> 00:46:12.600
All right, questions so far. Well, that's it. Now you know how to encode numbers. Somebody publishes this information. You take the thing you want to encode. You raise it to this power. You mod by the 17. The 17 is the prime. This power is the E. You have to know which numbers which. You don't want to do 6 to the 17. Mod 5. You have to know that this is E and this is the prime.
715
00:46:12.600 --> 00:46:22.600
So it's given to you in order. You're told that this is the exponent. This is the prime. That's how you do encoding. All right, questions so far.
716
00:46:22.600 --> 00:46:36.600
Question is how do you decode? And with this, we're going to come up with a whole issue of how to make sure the decoding is hard and coding is easy. If you have this information, how do you decode? You get 7. You're wondering what message was sent.
717
00:46:36.600 --> 00:46:45.600
I wonder what this person really meant. They really meant 6. But how do you figure out that they meant 6?
718
00:46:45.600 --> 00:47:01.600
The reverse function is very similar to this function. It's going to be 7 to the something mod 17. And in particular, the number here is going to be 13. That's the secret code.
719
00:47:01.600 --> 00:47:15.600
I'll call this private information. Private info is 13. 17. 17 is really public. So I'm going to circle the 13.
720
00:47:15.600 --> 00:47:25.600
The public needs one number and the prime number. The private person whose decoding needs the public prime and another special number.
721
00:47:25.600 --> 00:47:37.600
If you do 7 to the 13 mod 17, you get back to what you started. I'm going to tell you where that 13 comes from. And I'm going to tell you why this works.
722
00:47:37.600 --> 00:47:43.600
And then we're going to figure out how hard it would be to figure out 13 given just 5 and 17.
723
00:47:43.600 --> 00:47:51.600
So far, right now, this is just magic. You can check this and see that it works, but it does.
724
00:47:51.600 --> 00:48:06.600
So question so far.
725
00:48:06.600 --> 00:48:12.600
Let me show you where the 13 comes from. Then I'll show you why this works.
726
00:48:12.600 --> 00:48:35.600
Let's call that 13 D. Here's the 13. You want to pick a D, a private piece, such that when you multiply D and E, you get something congruent to 1 mod 16.
727
00:48:35.600 --> 00:48:44.600
If you're wondering why the hell would you want that? It's very important. This condition is what makes this thing work. And you'll see why in a second.
728
00:48:44.600 --> 00:48:55.600
But for now, let's just understand what it's saying. In our particular example, E is 5. So we want a number, such that 5 times that number is congruent to 1 mod 16.
729
00:48:55.600 --> 00:49:03.600
This 16 is 1 less than the prime we started. So if it was a general prime, it'd be P minus 1 there.
730
00:49:03.600 --> 00:49:21.600
Well, let's do this in our heads. What number times 5 is congruent to 1 mod 16? Well, the answer is 13. 5 times 13 is 65. If you divide 65 by 16, it goes in 4 times with a remainder of 1.
731
00:49:21.600 --> 00:49:29.600
That's how you get D. So it seems like it's hard. It seems like it's easy. We'll get back to that in a little while.
732
00:49:29.600 --> 00:49:36.600
But that's how you would compute D. And is the 5 from your public? The 5 is a public information, right?
733
00:49:36.600 --> 00:49:45.600
We'll get back later and figure out how to compute D in just 5 minutes. But let's go back here and see why this works. Are there questions so far?
734
00:49:45.600 --> 00:49:54.600
It's unique with respect to 16. You can add multiples of...
735
00:49:54.600 --> 00:50:06.600
You pick the one between 0 and 15. It's unique with mod 16.
736
00:50:06.600 --> 00:50:16.600
By the way, there doesn't even have to be a D. If 5 and 16 are not the greatest common divisor 1.
737
00:50:16.600 --> 00:50:30.600
The reason for that is that there's a solution to this equation. If 5 and 16 are not the greatest common divisor 1, if it's like 5 and 25 or something, then there might not even be a solution to this.
738
00:50:30.600 --> 00:50:35.600
So it's important that that condition is true at the beginning, so that we get a solution to this.
739
00:50:35.600 --> 00:50:41.600
We'll talk about this solution, how we do it in a couple minutes. But first, let's go back here and convince ourselves that this works.
740
00:50:41.600 --> 00:50:52.600
The reasoning that this works is the way that the real one is going to work. So concentrating on this next idea is going to help you just zoom through the actual idea in a couple of minutes.
741
00:50:52.600 --> 00:51:04.600
Why does this stuff work? Here's what we have to show. We have to show that if you take your hidden value, let's call it M, and you raise it to the 5th, 6 to the 5th.
742
00:51:04.600 --> 00:51:16.600
And then you take that, you get a 7, and then you take that 7, and you raise it to the 13th that you get back to what you started with.
743
00:51:16.600 --> 00:51:29.600
So we want to show that if I take M to the 5th, and then I raise it to the 13th, so M to the 5th to the 13th, that's M to the 5 times 13, that that's going to be congruent to...
744
00:51:29.600 --> 00:51:44.600
First to the 5th, and to the 13th, gets you back to... and gets you back to what you started with. Mod 16. Mod 17, sorry.
745
00:51:44.600 --> 00:51:52.600
If I can prove that to you, then I know encoding, followed by a decoding, is going to get you back to what you started.
746
00:51:52.600 --> 00:51:59.600
That this is going to be the encoding, and that's going to be the decoding, that they're inverse functions of each other.
747
00:51:59.600 --> 00:52:04.600
First due to the 5th, then due to the 13th, you start with 6, you end up with 6. Why is that true?
748
00:52:04.600 --> 00:52:09.600
I'm going to convince you this is true, and it's based on Fermat's little theorem.
749
00:52:09.600 --> 00:52:26.600
Questions so far? This 5 times 13, what do you know about it? What do you know about that 65?
750
00:52:26.600 --> 00:52:40.600
16 times 4 plus 1. How do I know that there's going to be a remainder of 1 here?
751
00:52:40.600 --> 00:52:49.600
Right? I constructed these two numbers 5 and 13 specifically, so that they would be a total of 1 more than 16.
752
00:52:49.600 --> 00:52:56.600
They would have a remainder of 1 with respect to 16, so when I multiply them together, I can write them as 4 times 16 plus 1.
753
00:52:56.600 --> 00:53:03.600
That comes from this computation.
754
00:53:03.600 --> 00:53:10.600
Now I have that n times, n to the 5 times 13 is n to the sum multiple of 16 plus 1.
755
00:53:10.600 --> 00:53:17.600
Where do I go from there? I've used my 1 main assumption. I'm out of assumptions. All I got left is Fermat's little theorem here.
756
00:53:17.600 --> 00:53:24.600
I better be close to done.
757
00:53:24.600 --> 00:53:41.600
m to the 16 times 4 plus 1 is m to the 16 times 4 times m. What do you know about this?
758
00:53:41.600 --> 00:53:49.600
If this turns into 1, congruent to mod 17, then we get m as our final answer.
759
00:53:49.600 --> 00:54:02.600
How do you know that this is going to be 1, mod 17? How do we know that m to the 16 times 4 is congruent to 1, mod 17?
760
00:54:02.600 --> 00:54:11.600
Fermat's theorem says, give me any number that's not divisible by 17, then m to the 16th is congruent to 1.
761
00:54:11.600 --> 00:54:15.600
That's what Fermat's theorem would say. The m to the 16th is congruent to 1.
762
00:54:15.600 --> 00:54:22.600
If m to the 16th is congruent to 1, then if I multiply it by itself 4 more times, it's just going to be 1 times 1 times 1 times 1.
763
00:54:22.600 --> 00:54:24.600
It's still going to be congruent to 1.
764
00:54:24.600 --> 00:54:34.600
This part is 1. This part is congruent to 1 by Fermat's last theorem. The whole thing m to the 65 is congruent to m.
765
00:54:34.600 --> 00:54:42.600
The whole thing works because this piece here ends up being 1 because of Fermat's last theorem.
766
00:54:42.600 --> 00:54:44.600
Questions about this?
767
00:54:44.600 --> 00:54:49.600
m is not divisible by 17.
768
00:54:49.600 --> 00:54:56.600
We pick a number so large that our m's are always smaller. If m was divisible by 17, this wouldn't necessarily work.
769
00:54:56.600 --> 00:54:59.600
So we make sure that m is smaller than 17. And we're safe.
770
00:54:59.600 --> 00:55:00.600
Yeah, Brian?
771
00:55:00.600 --> 00:55:06.600
I'm just telling a hard time wondering exactly what power to 1 seems like a silly problem.
772
00:55:06.600 --> 00:55:12.600
Does that mean that there's going to be some multiple of 1 in the remainder?
773
00:55:12.600 --> 00:55:16.600
It means that the remainder when you divide through by 17 is 1.
774
00:55:16.600 --> 00:55:26.600
If I take this, say, 6 to the 64th, and I subtract 1, and I divide it by 17, I get an even value.
775
00:55:26.600 --> 00:55:29.600
Clear? Makes sense?
776
00:55:29.600 --> 00:55:33.600
Other questions about this?
777
00:55:33.600 --> 00:55:37.600
Okay, so let's review. The public information is 5 and 17.
778
00:55:37.600 --> 00:55:43.600
The private information is 13 and 17. The 13 is the number that satisfies this equation.
779
00:55:43.600 --> 00:55:50.600
And I convinced you if I first go through and take my message and raise it to the 5th to that e,
780
00:55:50.600 --> 00:55:56.600
and I do a congruent mod 17, and then I raise it to the d, I get back to what I started with,
781
00:55:56.600 --> 00:56:01.600
because the multiples of 16 here end up being congruent to 1 mod 17.
782
00:56:01.600 --> 00:56:06.600
So the only thing that's left over is an m, which is what I started with here.
783
00:56:06.600 --> 00:56:09.600
So the whole thing works.
784
00:56:09.600 --> 00:56:14.600
These two are inverses of each other. It's a really cool thing.
785
00:56:14.600 --> 00:56:19.600
But the question is, how hard is it to figure out d once somebody's published 5 and 17?
786
00:56:19.600 --> 00:56:23.600
How hard is it to figure out 6 if somebody tells you 5 and 17?
787
00:56:23.600 --> 00:56:27.600
How hard is it to solve this equation?
788
00:56:27.600 --> 00:56:31.600
How hard is it to figure out 13?
789
00:56:31.600 --> 00:56:34.600
How hard is it to figure out 13? Right.
790
00:56:34.600 --> 00:56:39.600
Well, let's pretend we didn't tell you the answer was 13, and we try to solve this equation.
791
00:56:39.600 --> 00:56:54.600
What does this equation say? It says, find me d such that 5d minus 1 is the visible by 16.
792
00:56:54.600 --> 00:57:02.600
Right? Equal 16 times picoliter p, some multiple of 16.
793
00:57:02.600 --> 00:57:10.600
Or find me d and p such that 5d minus 16p equals 1.
794
00:57:10.600 --> 00:57:13.600
Have you ever done anything like this before?
795
00:57:13.600 --> 00:57:16.600
Yes, right? That's what we spent the whole day yesterday doing.
796
00:57:16.600 --> 00:57:20.600
You know that 5 and 16 have a greatest common divisor of 1.
797
00:57:20.600 --> 00:57:22.600
That was a big assumption we made.
798
00:57:22.600 --> 00:57:29.600
If it has a greatest common divisor of 1, you can find a d and a p to make this equation equal 1.
799
00:57:29.600 --> 00:57:40.600
So finding d given e is a straightforward as using Euclid's algorithm and doing a backward substitution.
800
00:57:40.600 --> 00:57:44.600
In fact, it's easy. It's not hard to get the inverse.
801
00:57:44.600 --> 00:57:49.600
If I publish 5 and 17, then anybody with a computer in about 3 seconds can say,
802
00:57:49.600 --> 00:57:53.600
hey, the private one is 13 and 17.
803
00:57:53.600 --> 00:57:57.600
So this is at the point where we need to just turn up the volume a little notch.
804
00:57:57.600 --> 00:58:08.600
The same exact idea can be milked one step further where the computation of the 13 becomes very hard instead of very easy.
805
00:58:08.600 --> 00:58:10.600
Okay? So here's the main idea.
806
00:58:10.600 --> 00:58:14.600
So stick with me. Don't get tired right now. This is the most important part.
807
00:58:14.600 --> 00:58:19.600
The next step does this. It publishes, instead of publishing 5 and 17,
808
00:58:19.600 --> 00:58:25.600
it's going to publish 5 and some big, big, big number which is not prime.
809
00:58:25.600 --> 00:58:29.600
I'm not going to use a big number because it's going to be impossible to show you the example.
810
00:58:29.600 --> 00:58:32.600
I'm going to use a small number, but you can imagine that the number is very big.
811
00:58:32.600 --> 00:58:37.600
I'm going to publish the number 34.
812
00:58:37.600 --> 00:58:47.600
Normally, you would publish a number which is a product of 2 128-bit prime numbers.
813
00:58:47.600 --> 00:58:55.600
Okay? A huge number which has huge factors, hard to factor. I'm publishing 34.
814
00:58:55.600 --> 00:58:58.600
You could all factor it to 2 and 17.
815
00:58:58.600 --> 00:59:01.600
I'm going to convince you we're going to do the same similar trick,
816
00:59:01.600 --> 00:59:06.600
but when this number is published, we can't do anything until this number gets factored.
817
00:59:06.600 --> 00:59:11.600
Since we can factor this number, we'll be able to go through the whole thing and recompute the private key.
818
00:59:11.600 --> 00:59:14.600
But if you couldn't factor this number, you'd be stuck.
819
00:59:14.600 --> 00:59:18.600
I'm going to show you why and what point this all happens in just a second.
820
00:59:18.600 --> 00:59:22.600
That's where we're headed. Questions about this.
821
00:59:22.600 --> 00:59:26.600
The private key is no longer known. It's a mystery.
822
00:59:26.600 --> 00:59:32.600
Now we've published 5 and 34.
823
00:59:32.600 --> 00:59:38.600
Just as before, if you want to encode 6, it's 6 to the 5th, but this time it's mod 34.
824
00:59:38.600 --> 00:59:43.600
Instead of mod a prime number, now it's mod some other big number which is a product of 2 prime.
825
00:59:43.600 --> 00:59:53.600
I'm going to write here a product of 2 large prime numbers.
826
00:59:53.600 --> 00:59:57.600
This is not a great example of that. 2 and 17 are not large.
827
00:59:57.600 --> 00:59:59.600
2 is about the smallest prime number you can get.
828
00:59:59.600 --> 01:00:03.600
But normally these are 2 really big prime numbers. You multiply them together.
829
01:00:03.600 --> 01:00:07.600
So there's only 2 factors in this huge number.
830
01:00:07.600 --> 01:00:09.600
Finding them would be hard.
831
01:00:09.600 --> 01:00:13.600
And you encode the same way. And you're going to decode in a similar way.
832
01:00:13.600 --> 01:00:17.600
6 to something mod 34.
833
01:00:17.600 --> 01:00:23.600
And I'll tell you the secret. The secret is that the private code here is also 13.
834
01:00:23.600 --> 01:00:27.600
So you would decode this way.
835
01:00:27.600 --> 01:00:33.600
Actually this ends up decaling.
836
01:00:33.600 --> 01:00:37.600
Did I do this one?
837
01:00:37.600 --> 01:00:47.600
Hold on. I'm looking at my numerals. I don't remember.
838
01:00:47.600 --> 01:00:55.600
But I'll just write it this way. I'll call this x. I'll call this x.
839
01:00:55.600 --> 01:00:59.600
So encode your raise to the 5th power to decode your raise to the 13th power.
840
01:00:59.600 --> 01:01:01.600
The question is, how do you find out this 13?
841
01:01:01.600 --> 01:01:05.600
The computation of the 13 in this situation is going to be harder.
842
01:01:05.600 --> 01:01:09.600
It's going to have us require it to be able to factor these numbers.
843
01:01:09.600 --> 01:01:11.600
Yeah, Ej.
844
01:01:11.600 --> 01:01:13.600
You don't use x on the key.
845
01:01:13.600 --> 01:01:17.600
No, I'm just saying take whatever you want and you decode it this way.
846
01:01:17.600 --> 01:01:21.600
It's not the same. I'll call it y.
847
01:01:21.600 --> 01:01:25.600
Yeah, this would be m and this would be m inverse.
848
01:01:25.600 --> 01:01:29.600
I should use a different letter.
849
01:01:29.600 --> 01:01:33.600
Okay.
850
01:01:33.600 --> 01:01:37.600
Set.
851
01:01:37.600 --> 01:01:39.600
What's 24 of this?
852
01:01:39.600 --> 01:01:41.600
60 codes to 24.
853
01:01:41.600 --> 01:01:45.600
60 codes to 24 and this would codes back to 6.
854
01:01:45.600 --> 01:01:51.600
I don't think we need it, but we can go on.
855
01:01:51.600 --> 01:01:53.600
Where does this 34 come from? I said it comes from two primes.
856
01:01:53.600 --> 01:01:57.600
In this case, you know the primes are, we'll call them p and q.
857
01:01:57.600 --> 01:02:01.600
2 and 17.
858
01:02:01.600 --> 01:02:11.600
Before we subtracted one from our single prime, in the two prime situation,
859
01:02:11.600 --> 01:02:15.600
we're going to subtract one from each of these.
860
01:02:15.600 --> 01:02:22.600
So we get p minus 1 times q minus 1, and that's 1 times 16 and that equals 16.
861
01:02:22.600 --> 01:02:25.600
I set this up so we get the same 16 that we got before,
862
01:02:25.600 --> 01:02:29.600
so we don't have to do a lot more calculations that we get the same 13.
863
01:02:29.600 --> 01:02:33.600
But normally you would find the two primes, you'd subtract one from each,
864
01:02:33.600 --> 01:02:37.600
you would get 16.
865
01:02:37.600 --> 01:02:41.600
And now you would solve the following problem.
866
01:02:41.600 --> 01:02:53.600
5 times D is congruent to 1 mod 16.
867
01:02:53.600 --> 01:02:56.600
Same thing we did before.
868
01:02:56.600 --> 01:03:02.600
And D is therefore 13 by using the same methods we did before.
869
01:03:02.600 --> 01:03:08.600
The difference here is that we didn't get to this equation until we did this step over here.
870
01:03:08.600 --> 01:03:12.600
We didn't know this number 16 until we first did what?
871
01:03:12.600 --> 01:03:19.600
Until we first took 34, factored it out, subtracted one from each, and multiplied them together.
872
01:03:19.600 --> 01:03:25.600
You can't get to this point until you factor a very big number.
873
01:03:25.600 --> 01:03:29.600
This step here is the slow step.
874
01:03:29.600 --> 01:03:34.600
We can't figure out D until we do this factoring of 34.
875
01:03:34.600 --> 01:03:36.600
Factoring is a very hard thing to do.
876
01:03:36.600 --> 01:03:41.600
You take two huge numbers, multiply them together, get something here,
877
01:03:41.600 --> 01:03:44.600
and then give it to somebody and say what two numbers that I start with,
878
01:03:44.600 --> 01:03:48.600
and they can sit for three weeks and they won't be able to do it.
879
01:03:48.600 --> 01:03:54.600
So multiplying two prime numbers is easy, extracting them once they're multiplied together is very hard.
880
01:03:54.600 --> 01:03:58.600
So I need to still convince you that this does the inverse of this.
881
01:03:58.600 --> 01:04:02.600
That if you do x to the fifth and then you do x to the 13th that you still get back to x,
882
01:04:02.600 --> 01:04:06.600
even if you do it in this peculiar way,
883
01:04:06.600 --> 01:04:12.600
where the D is computed via the 16, which came from a p minus 1, q minus 1,
884
01:04:12.600 --> 01:04:14.600
instead of just the original single problem.
885
01:04:14.600 --> 01:04:16.600
Why does the whole thing still work?
886
01:04:16.600 --> 01:04:18.600
And that's going to wrap the whole thing up.
887
01:04:18.600 --> 01:04:20.600
So before I do that, let me stop for final questions.
888
01:04:20.600 --> 01:04:23.600
Then I'll do that. It'll take five or ten minutes and we'll be done.
889
01:04:23.600 --> 01:04:25.600
Are there any questions so far?
890
01:04:25.600 --> 01:04:29.600
We set it up the first way, just relative to a single prime,
891
01:04:29.600 --> 01:04:34.600
and it turned out that it ended up with this equation which we could calculate the private value for.
892
01:04:34.600 --> 01:04:37.600
How do we calculate the...
893
01:04:37.600 --> 01:04:42.600
The same way we did before. You calculate 5D minus 16P equals 1.
894
01:04:42.600 --> 01:04:45.600
You calculate two values to make this true.
895
01:04:45.600 --> 01:04:48.600
And that's what we did yesterday with Euclid's algorithm.
896
01:04:48.600 --> 01:04:50.600
The same exact way we did it before.
897
01:04:50.600 --> 01:04:53.600
The question is, how did we know it should be 16?
898
01:04:53.600 --> 01:04:58.600
And that takes a lot of work, because we have to factor to find that 16.
899
01:04:58.600 --> 01:05:02.600
So you get all the known prime numbers sitting somewhere,
900
01:05:02.600 --> 01:05:06.600
and you could just stand marked like a final.
901
01:05:06.600 --> 01:05:10.600
Yes, a lot of prime numbers.
902
01:05:10.600 --> 01:05:15.600
You mean your idea of factoring two large numbers to try every pair of primes and see if they work?
903
01:05:15.600 --> 01:05:21.600
I mean, look at the number of digits.
904
01:05:21.600 --> 01:05:24.600
That's an algorithm in it would take a long time.
905
01:05:24.600 --> 01:05:30.600
Yeah.
906
01:05:30.600 --> 01:05:35.600
Let's check this and see that it works, and then I'll stop for final questions and we'll wrap up.
907
01:05:35.600 --> 01:05:40.600
The 34 you have here is the 16 here.
908
01:05:40.600 --> 01:05:43.600
The 34 is what's published now.
909
01:05:43.600 --> 01:05:49.600
And the 16 is calculated from a factoring that lets me calculate the private code.
910
01:05:49.600 --> 01:05:54.600
The private code comes from this equation with respect to 16.
911
01:05:54.600 --> 01:06:00.600
The 16 was calculated by factoring the numbers and subtracting one from each and multiplying them together.
912
01:06:00.600 --> 01:06:02.600
Oh, and the two times 17 is 34.
913
01:06:02.600 --> 01:06:06.600
Right, the two times 17 came from factoring the 34.
914
01:06:06.600 --> 01:06:10.600
So the only thing left to show is that this whole thing still works.
915
01:06:10.600 --> 01:06:15.600
That the y to the 13th is really the inverse of the x to the 5.
916
01:06:15.600 --> 01:06:17.600
That they really are backwards.
917
01:06:17.600 --> 01:06:19.600
That they do the opposites of each other.
918
01:06:19.600 --> 01:06:21.600
So let's go through the argument again.
919
01:06:21.600 --> 01:06:24.600
Because it's the same argument as before with one little twist.
920
01:06:24.600 --> 01:06:26.600
5d is congruent to 1 mod 16.
921
01:06:26.600 --> 01:06:32.600
5 times 13, 65 is congruent to 1 is remainder of 1 with respect to 16.
922
01:06:32.600 --> 01:06:35.600
The same reason is before.
923
01:06:35.600 --> 01:06:37.600
Because of this equation.
924
01:06:37.600 --> 01:06:40.600
So here it's the same argument as before.
925
01:06:40.600 --> 01:06:43.600
We want to show now that this whole thing is 1.
926
01:06:43.600 --> 01:06:46.600
But this time we want to show that it's 1 not congruent to 17,
927
01:06:46.600 --> 01:06:49.600
which is immediately from Frommas little theorem.
928
01:06:49.600 --> 01:06:53.600
We want to show that this is congruent to 1 mod 34.
929
01:06:53.600 --> 01:06:56.600
Everybody see the difference?
930
01:06:56.600 --> 01:06:59.600
That's the only place where we have to make a different argument.
931
01:06:59.600 --> 01:07:02.600
So I'm going to write this down over here, get a little bit of room,
932
01:07:02.600 --> 01:07:03.600
and analyze it.
933
01:07:03.600 --> 01:07:06.600
Because it's not too tough.
934
01:07:06.600 --> 01:07:13.600
We're hoping that x to the 4 times 16 is congruent to 1 mod 34.
935
01:07:13.600 --> 01:07:15.600
If that's true, we're all set.
936
01:07:15.600 --> 01:07:21.600
Now we know that it's congruent to 1 mod 17.
937
01:07:21.600 --> 01:07:25.600
Because Frommas less theorem says you put a 17 there,
938
01:07:25.600 --> 01:07:30.600
and x to the 16th is going to be 1.
939
01:07:30.600 --> 01:07:32.600
Multiple of it are also going to be 1.
940
01:07:32.600 --> 01:07:35.600
So now what happens with the 34 there?
941
01:07:35.600 --> 01:07:36.600
We just did.
942
01:07:36.600 --> 01:07:37.600
I mean, it still works out.
943
01:07:37.600 --> 01:07:44.600
So how can we prove that it works out?
944
01:07:44.600 --> 01:07:53.600
Well, let me write down what we do now.
945
01:07:53.600 --> 01:07:58.600
We know this is true.
946
01:07:58.600 --> 01:08:08.600
That's from before.
947
01:08:08.600 --> 01:08:10.600
What about this?
948
01:08:10.600 --> 01:08:17.600
Is that true?
949
01:08:17.600 --> 01:08:21.600
If it is y and if it's not y-not,
950
01:08:21.600 --> 01:08:23.600
is that going to be true?
951
01:08:23.600 --> 01:08:25.600
That the other prime number?
952
01:08:25.600 --> 01:08:28.600
No, it's going to be even number.
953
01:08:28.600 --> 01:08:43.600
Because x to the 16th is going to be 16 is 2 minus 1 times 17 minus 1.
954
01:08:43.600 --> 01:08:47.600
Let's look at Ej's idea.
955
01:08:47.600 --> 01:08:54.600
You want to write 16 as 2 minus 1 times 17 minus 1.
956
01:08:54.600 --> 01:09:03.600
In other words, it's the same as 1 times 16.
957
01:09:03.600 --> 01:09:06.600
What Ej's pointing out, where do we get the 16 from?
958
01:09:06.600 --> 01:09:16.600
It was p minus 1 times q minus 1.
959
01:09:16.600 --> 01:09:18.600
So it's 4 times 16.
960
01:09:18.600 --> 01:09:20.600
Maybe it's hard to see it with the 2.
961
01:09:20.600 --> 01:09:25.600
What if it was, let me stick with the 2.
962
01:09:25.600 --> 01:09:30.600
That's 16 times 1.
963
01:09:30.600 --> 01:09:32.600
So let's try to use for my little theorem again.
964
01:09:32.600 --> 01:09:38.600
If there's a 2 here, what number can you put here?
965
01:09:38.600 --> 01:09:41.600
What exponent can you use?
966
01:09:41.600 --> 01:09:43.600
1 less than it.
967
01:09:43.600 --> 01:09:45.600
So there is a 1 explicitly there.
968
01:09:45.600 --> 01:09:47.600
We don't write it in.
969
01:09:47.600 --> 01:09:51.600
16 times 1 is 6 p minus 1 times q minus 1.
970
01:09:51.600 --> 01:10:01.600
So for my last little theorem says that x to the 1 is congruent to 1 minus 2.
971
01:10:01.600 --> 01:10:06.600
So multiples of that are also going to be congruent to 1 minus 2.
972
01:10:06.600 --> 01:10:08.600
This is completely symmetric.
973
01:10:08.600 --> 01:10:12.600
p minus 1 and q minus 1 are together making up 16.
974
01:10:12.600 --> 01:10:15.600
So they both appear here times 4.
975
01:10:15.600 --> 01:10:19.600
This one's going to be congruent to 1 minus 17 because 16 is 1 less.
976
01:10:19.600 --> 01:10:22.600
And this is going to be congruent to 1 minus 2 because 1 is 1 less.
977
01:10:22.600 --> 01:10:26.600
I want to show that x to the 64th is congruent to 1 minus 34.
978
01:10:26.600 --> 01:10:31.600
And all I've shown now is that it's congruent to 1 minus 17 and congruent to 1 minus 2.
979
01:10:31.600 --> 01:10:33.600
Let's remind ourselves what this means.
980
01:10:33.600 --> 01:10:36.600
It means I've got some big ugly number here.
981
01:10:36.600 --> 01:10:38.600
I don't care what it is. Call it whatever you want.
982
01:10:38.600 --> 01:10:39.600
x to the 64th.
983
01:10:39.600 --> 01:10:40.600
Let's give it a name.
984
01:10:40.600 --> 01:10:44.600
Let's call it b for big and ugly.
985
01:10:44.600 --> 01:10:53.600
I know that b minus 1 is the visible by 17 and b minus 1 is the visible by 2.
986
01:10:53.600 --> 01:10:58.600
Okay, the b is x to the 64th.
987
01:10:58.600 --> 01:11:00.600
You got some big number.
988
01:11:00.600 --> 01:11:02.600
It's the visible by 17.
989
01:11:02.600 --> 01:11:03.600
That's a prime.
990
01:11:03.600 --> 01:11:04.600
It's the visible by 2.
991
01:11:04.600 --> 01:11:07.600
That's another prime.
992
01:11:07.600 --> 01:11:13.600
Therefore, the b is x to the 64th.
993
01:11:13.600 --> 01:11:20.600
That's the b.
994
01:11:20.600 --> 01:11:25.600
If you ever have two prime numbers and they each divide into some other number,
995
01:11:25.600 --> 01:11:30.600
then their product also asks to divide into that number.
996
01:11:30.600 --> 01:11:33.600
You can prove that if you want to, but it's kind of logical.
997
01:11:33.600 --> 01:11:36.600
One is it's not, what if they're not prime?
998
01:11:36.600 --> 01:11:39.600
Can you give an example where it doesn't work?
999
01:11:39.600 --> 01:11:43.600
What if four divides into a number and six divides into a number?
1000
01:11:43.600 --> 01:11:46.600
Does 24 divide into the number?
1001
01:11:46.600 --> 01:11:49.600
Four divides into 12.
1002
01:11:49.600 --> 01:11:50.600
Six divides into 12.
1003
01:11:50.600 --> 01:11:52.600
24 doesn't divide into 12.
1004
01:11:52.600 --> 01:11:53.600
Because they're composite.
1005
01:11:53.600 --> 01:11:56.600
So little pieces of this can combine together in a way that you wouldn't
1006
01:11:56.600 --> 01:11:59.600
necessarily expect there's overlap in the factors.
1007
01:11:59.600 --> 01:12:02.600
But if these two are prime and they each divide into here,
1008
01:12:02.600 --> 01:12:05.600
that means that prime factor has to be a part of this.
1009
01:12:05.600 --> 01:12:07.600
And this prime factor has to be a part of this.
1010
01:12:07.600 --> 01:12:10.600
So their product must also divide into it.
1011
01:12:10.600 --> 01:12:15.600
Therefore, 34 also divides into x to the 64th minus 1.
1012
01:12:15.600 --> 01:12:20.600
34 also divides into b minus 1.
1013
01:12:20.600 --> 01:12:23.600
Therefore, this is true.
1014
01:12:23.600 --> 01:12:27.600
Because these two numbers, 17 and 2 are prime.
1015
01:12:27.600 --> 01:12:28.600
Four, yeah.
1016
01:12:28.600 --> 01:12:36.600
That's still like how we prove that it would, that x to the 64th is what we're going to do.
1017
01:12:36.600 --> 01:12:39.600
It's also by Fermat's little theorem.
1018
01:12:39.600 --> 01:12:42.600
By Fermat's little theorem, if there's a 2 here,
1019
01:12:42.600 --> 01:12:48.600
then anything to the 1 is going to be congruent to 1.
1020
01:12:48.600 --> 01:12:50.600
So x to the anything is congruent to 1.
1021
01:12:50.600 --> 01:12:53.600
x to the 1 is congruent to 1.
1022
01:12:53.600 --> 01:12:56.600
Multiple of that will also be congruent to 1.
1023
01:12:56.600 --> 01:12:58.600
It may be not the best example to see it with a 2,
1024
01:12:58.600 --> 01:13:01.600
but pretend this was a 15 instead of a 2.
1025
01:13:01.600 --> 01:13:07.600
Then the number here would be 4 times 16 times 14.
1026
01:13:07.600 --> 01:13:10.600
And then there would be a 14 here and a 15 here.
1027
01:13:10.600 --> 01:13:14.600
And then it would work the same way.
1028
01:13:14.600 --> 01:13:16.600
The trick here, it's really kind of,
1029
01:13:16.600 --> 01:13:17.600
I showed you the first case,
1030
01:13:17.600 --> 01:13:20.600
because the first case was around before the second case was.
1031
01:13:20.600 --> 01:13:25.600
And the real breakthrough was really a simple idea.
1032
01:13:25.600 --> 01:13:29.600
It was just taking the first case, adding an extra prime minus 1,
1033
01:13:29.600 --> 01:13:32.600
instead of p minus 1, throwing a factor of q minus 1.
1034
01:13:32.600 --> 01:13:35.600
And everything works exactly the same as it did before,
1035
01:13:35.600 --> 01:13:38.600
except now, before you can solve for that d,
1036
01:13:38.600 --> 01:13:42.600
you need to factor these numbers to get your p minus 1 times q minus 1.
1037
01:13:42.600 --> 01:13:46.600
And it's that factoring step that makes the whole thing hard.
1038
01:13:46.600 --> 01:13:48.600
So it was a clever way of taking something that worked before
1039
01:13:48.600 --> 01:13:51.600
that had an easy inverse, doing a teeny twist on it,
1040
01:13:51.600 --> 01:13:54.600
and making it have a really hard inverse.
1041
01:13:54.600 --> 01:13:56.600
And this is exactly what's used today.
1042
01:13:56.600 --> 01:13:59.600
The numbers they choose are typically,
1043
01:13:59.600 --> 01:14:05.600
this is what you go by in your new browsers, 128-bit encryption,
1044
01:14:05.600 --> 01:14:08.600
which means that after you multiply these two numbers together,
1045
01:14:08.600 --> 01:14:12.600
the two large primes, you get a number that's 128-bits long.
1046
01:14:12.600 --> 01:14:16.600
So that's how many base 10 digits is that?
1047
01:14:16.600 --> 01:14:21.600
Base 2, it's 128-bits, so it's about three points,
1048
01:14:21.600 --> 01:14:24.600
something digits for 10.
1049
01:14:24.600 --> 01:14:27.600
So 40 or so?
1050
01:14:27.600 --> 01:14:29.600
It's not like that.
1051
01:14:29.600 --> 01:14:31.600
40-some-odd-based 10 digits.
1052
01:14:31.600 --> 01:14:33.600
So it's a very big number.
1053
01:14:33.600 --> 01:14:35.600
And you have to be able to factor that.
1054
01:14:35.600 --> 01:14:40.600
And I think that's on the order of 50 years to factor 128-bit.
1055
01:14:40.600 --> 01:14:45.600
That's just a small, you can get 4,086 on one of these 8-bits.
1056
01:14:45.600 --> 01:14:48.600
Aha. So that's like centuries.
1057
01:14:48.600 --> 01:14:50.600
Right, that's centuries.
1058
01:14:50.600 --> 01:14:52.600
As far as anybody knows, maybe there's a good way to factor numbers.
1059
01:14:52.600 --> 01:14:56.600
If you come up with an algorithm that's polynomial for factoring numbers,
1060
01:14:56.600 --> 01:14:58.600
that'd be really interesting.
1061
01:14:58.600 --> 01:15:03.600
And I got to tell you, for those people who sit around and try to solve NP-complete problems,
1062
01:15:03.600 --> 01:15:07.600
you're a lot more likely to find a polynomial algorithm for prime numbers,
1063
01:15:07.600 --> 01:15:13.600
in some sense, than you are to find a polynomial algorithm for an NP-complete problem.
1064
01:15:13.600 --> 01:15:16.600
Because prime numbers aren't NP-complete.
1065
01:15:16.600 --> 01:15:18.600
So maybe there's a chance.
1066
01:15:18.600 --> 01:15:21.600
I should say there's another reason why you wouldn't expect the polynomial number
1067
01:15:21.600 --> 01:15:23.600
for prime numbers, but it's a little complicated.
1068
01:15:23.600 --> 01:15:25.600
The complement of the problem is, forget it.
1069
01:15:25.600 --> 01:15:27.600
Well, we'll do it in a theory of computation.
1070
01:15:27.600 --> 01:15:28.600
Yeah.
1071
01:15:28.600 --> 01:15:31.600
So the people who changed encryption key,
1072
01:15:31.600 --> 01:15:33.600
they'll be on the parallel.
1073
01:15:33.600 --> 01:15:35.600
I don't know. I don't know what's really done.
1074
01:15:35.600 --> 01:15:37.600
I don't know what companies really do.
1075
01:15:37.600 --> 01:15:38.600
It flips with every request.
1076
01:15:38.600 --> 01:15:40.600
That's how secure, like, HTTPS works.
1077
01:15:40.600 --> 01:15:42.600
So the key change is at every request.
1078
01:15:42.600 --> 01:15:45.600
So any time you send your credit card number,
1079
01:15:45.600 --> 01:15:48.600
it's using a different key to encode it.
1080
01:15:48.600 --> 01:15:52.600
And actually, there's a transaction sequence where a writing encryption is used
1081
01:15:52.600 --> 01:15:56.600
on a pre-key that builds up a heavier encryption with another key,
1082
01:15:56.600 --> 01:16:00.600
the builds up the transaction encryption scheme.
1083
01:16:00.600 --> 01:16:02.600
Oh, that's interesting.
1084
01:16:02.600 --> 01:16:08.600
I mean, actually, when you encrypt anything,
1085
01:16:08.600 --> 01:16:10.600
I mean, we did these examples with just a single number
1086
01:16:10.600 --> 01:16:12.600
of being converted to another number.
1087
01:16:12.600 --> 01:16:15.600
But what typically happens is you get these kind of partial sums in a message.
1088
01:16:15.600 --> 01:16:19.600
Your message is a collection of these numbers.
1089
01:16:19.600 --> 01:16:21.600
So you encrypt the first one,
1090
01:16:21.600 --> 01:16:24.600
and then you connect that with the next one
1091
01:16:24.600 --> 01:16:27.600
to give you a larger number, then you encrypt that.
1092
01:16:27.600 --> 01:16:30.600
And you connect that encrypted one with the next one to give you a larger one.
1093
01:16:30.600 --> 01:16:33.600
So you embed the encryption's one and another,
1094
01:16:33.600 --> 01:16:36.600
rather than just encrypting them, I think, one at a time.
1095
01:16:36.600 --> 01:16:38.600
So if you have, like, a sequence of 100 numbers,
1096
01:16:38.600 --> 01:16:41.600
you just don't encrypt each number one at a time and send them.
1097
01:16:41.600 --> 01:16:45.600
And you encrypt one.