0:00:00.000,0:00:04.220
In the previous segment we talked about[br]modular inversion and we said the Euclid's

0:00:04.220,0:00:08.238
algorithm gives us an efficient way to[br]find the inverse of an element modulo N.

0:00:08.238,0:00:12.256
In this segment we're going to forward[br]through time and we're going to move to

0:00:12.256,0:00:15.866
the seventeenth and eighteenth century[br]where we're going to talk about

0:00:15.866,0:00:19.986
Fermat and Euler contributions.[br]Before that let's do a quick review of

0:00:19.986,0:00:24.257
what we discussed in the previous segment.[br]So as usual I'm going to let N denote the

0:00:24.257,0:00:28.427
positive integer and let's just say that N[br]happens to be a n-bit integer, in other

0:00:28.427,0:00:32.445
words it's between two to the n and two to[br]the n+1, as usual we're going to let P

0:00:32.445,0:00:36.761
denote a prime. Now we said that[br]ZN is a set of integers from zero

0:00:36.761,0:00:41.370
to N-1 and we said that we can add and[br]multiply elements in the set modulo N. We

0:00:41.370,0:00:46.186
also said that ZN star is basically the[br]set of invertible elements in ZN. And we

0:00:46.186,0:00:51.243
proved a simple lemma to say that, X is[br]invertible if and only if X is relatively

0:00:51.243,0:00:55.879
prime to N. And not only did we[br]completely understand which elements are

0:00:55.879,0:01:00.635
invertible and which aren't, we also[br]showed a very efficient algorithm based on

0:01:00.635,0:01:05.572
Euclid's extended algorithm, to find the[br]inverse of an element X in ZN. And we said

0:01:05.572,0:01:10.388
that the running time of this algorithm,[br]is basically order n squared, where

0:01:10.388,0:01:16.107
again, n is the number of bits of the[br]number capital N. So as I said, now

0:01:16.107,0:01:21.037
we're going to move from Greek times all[br]the way to the seventeenth century and

0:01:21.037,0:01:26.276
talk about Fermat. So Fermat did a number[br]of important theorems. The one that I want

0:01:26.276,0:01:31.206
to show you here today is the following.[br]So suppose I give you a prime P. Then in

0:01:31.206,0:01:36.260
fact for any element X in ZP star, it so[br]happens that if I look at X and raise it

0:01:36.260,0:01:41.130
to the power of P - 1, I'm a gonna get[br]one, in ZP. So let's look at a quick

0:01:41.130,0:01:46.061
example. Suppose I set the number P to be[br]five. And I look at, three to the power of

0:01:46.061,0:01:50.645
P-1. In other words, three to the power of[br]four, Three to the power of four is 81,

0:01:50.645,0:01:55.286
which in fact, is one modulo five. This[br]example satisfies Fermat's theorem.

0:01:55.286,0:01:59.521
Interestingly, Fermat actually didn't prove this theorem himself. The proof

0:01:59.521,0:02:04.337
actually waited until Euler, who[br]proved that almost 100 years later. And in

0:02:04.337,0:02:09.122
fact, he proved a much more general[br]version of this theorem. So let's look at

0:02:09.122,0:02:14.154
a simple application of Fermat's theorem.[br]Suppose I look at an element X in Z P

0:02:14.154,0:02:19.441
star. And I want to remind you here that P[br][inaudible] must be a prime. Well, then what do we

0:02:19.441,0:02:24.664
know? We know that X to the P minus one is[br]equal to one. Well, we can write X to the

0:02:24.664,0:02:29.573
P minus one as X times X to the power of P[br]minus two. Well so now we know that X

0:02:29.573,0:02:34.087
times X to the power of P minus two[br]happens to be equal to one. And what that

0:02:34.087,0:02:39.310
says, is that really the inverse of X[br]modulo P, is simply X to the P minus two.

0:02:39.310,0:02:44.042
So this gives us another algorithm for[br]finding the inverse of X modulo a prime.

0:02:44.042,0:02:48.835
Simply raise X to the power of p minus[br]two, and that will give us the inverse of

0:02:48.835,0:02:53.508
x. It turns out, actually this is a fine[br]way to compute inverses modulo a prime.

0:02:53.508,0:02:58.301
But it has two deficiencies compared to[br]Euclid's algorithm. First of all, it only

0:02:58.301,0:03:02.528
works modulo primes, Whereas, Euclid's[br]algorithm worked modulo composites as

0:03:02.528,0:03:07.017
well. And second of all, it turns out this[br]algorithm is actually less efficient. When

0:03:07.017,0:03:10.911
we talk about how to do modular[br]exponentiations--we're gonna do that in

0:03:10.911,0:03:15.345
the last segment in this module--you'll[br]see that the running time to compute this

0:03:15.345,0:03:19.792
exponentiation is actually cubic in the[br]size of P. So this will take roughly log

0:03:19.792,0:03:24.266
cube of P, whereas if you remember,[br]Euclid's algorithm was able to compute the

0:03:24.266,0:03:30.343
inverse in quadratic time in the[br]representation of P. So not only is this

0:03:30.343,0:03:36.512
algorithm less general it only works for[br]primes, it's also less efficient. So score

0:03:36.512,0:03:41.473
one for Euclid. But nevertheless, this[br]fact about primes is extremely important,

0:03:41.473,0:03:47.506
and we're gonna be making extensive use of[br]it in the next couple of weeks. So let me

0:03:47.506,0:03:52.155
show you a quick and simple application[br]for Fermat's theorem suppose we wanted

0:03:52.155,0:03:57.226
to generate a large random prime, say our[br]prime needed to be 1,000 bits or so. So

0:03:57.226,0:04:02.006
the prime we're looking for is on the[br]order of two to the 1024 [inaudible]. So here's

0:04:02.006,0:04:06.724
a very simple probabilistic algorithm.[br]What we would do is we would choose a

0:04:06.724,0:04:11.938
random integer in the interval that was[br]specified. And then we would test whether

0:04:12.124,0:04:17.153
this integer satisfies Fermat's theorem.[br]In other words, we would test for example

0:04:17.153,0:04:22.367
using the base two; we would test whether[br]two to the power of p minus one equals one

0:04:22.367,0:04:27.271
in Z p. If the answer is no, then if this[br]equality doesn't hold, then we know for

0:04:27.271,0:04:33.003
sure that the number p that we chose is[br]not a prime. And if that happens, all we

0:04:33.003,0:04:37.284
do is we go back to step one and we try[br]another prime. And we do this again and

0:04:37.284,0:04:41.782
again and again, until finally we find an[br]integer that satisfies this condition. And

0:04:41.782,0:04:46.009
once we find an integer that satisfies[br]this condition, we simply output it and

0:04:46.009,0:04:51.573
stop. Now it turns out, this is actually a[br]fairly difficult statement to prove. But

0:04:51.573,0:04:56.305
it turns out if a random number passes[br]this test, then it's extremely likely to

0:04:56.305,0:05:01.398
be a prime. In particular the probability[br]that P is not a prime is very small. It's

0:05:01.398,0:05:06.191
like less than two to the -60 for the[br]range of 1024 bit numbers. As the

0:05:06.191,0:05:10.744
number gets bigger and bigger the[br]probability that it passes this test here,

0:05:10.744,0:05:15.716
but is not a prime drops to zero very[br]quickly. So this is actually quite an

0:05:15.716,0:05:20.455
interesting algorithm. You realize we're[br]not guaranteed that the output is in fact

0:05:20.455,0:05:25.021
a prime. All we know is that it's very,[br]very likely to be a prime. In other words

0:05:25.021,0:05:29.587
the only way that it's not a prime is that[br]we got extremely unlucky. In fact so

0:05:29.587,0:05:34.298
unlucky that a negligible probability[br]event just happened. Another way to say

0:05:34.298,0:05:40.230
this is that if you look at the set of all[br]1024 integers, then, well, there's the set

0:05:40.230,0:05:45.233
of primes. Let me write prime here. And[br]then there is a small number of

0:05:45.233,0:05:50.805
composites. That actually will falsify the[br]test. Let's call them F for false primes.

0:05:50.805,0:05:55.653
Let's call them FP, for false primes.[br]There's a very small number of composites

0:05:55.653,0:06:00.626
that are not prime and yet will pass this[br]test. But as we choose random integers,

0:06:00.626,0:06:05.349
you know, we choose one here, one here,[br]one here, and so on, as we choose random

0:06:05.349,0:06:10.260
integers, the probability that we fall[br]into the set of false primes is so small

0:06:10.260,0:06:15.082
That it's essentially a negligible event[br]that we can ignore. In other words, one

0:06:15.082,0:06:20.591
can prove that the set of false primes is[br]extremely small, and a random choice is

0:06:20.591,0:06:25.266
unlikely to pick such a false prime. Now I[br]should mention, in fact, this is a very

0:06:25.266,0:06:28.960
simple algorithm for generating primes.[br]It's actually, by far, not the best

0:06:28.960,0:06:32.654
algorithm. We have much better algorithms[br]now. And, in fact, once you have a

0:06:32.654,0:06:36.349
candidate prime, we now have very[br]efficient algorithms that will actually

0:06:36.349,0:06:40.498
prove beyond a doubt that this candidate[br]prime really is a prime. So we don't even

0:06:40.498,0:06:44.597
have to rely on probabilistic statements.[br]But nevertheless, this Fermat test is so

0:06:44.597,0:06:48.595
simple, that I just wanted to show you[br]that it's an easy way to generate primes.

0:06:48.595,0:06:53.076
Although in reality, this is not how[br]primes are generated. As the last point,

0:06:53.076,0:06:57.468
I'll say that you might be wondering how[br]many times this iteration has to repeat

0:06:57.468,0:07:01.536
until we actually find the prime. And[br]that's actually a classic result; it's

0:07:01.536,0:07:05.820
called the prime number theorem, which[br]says that, after a few hundred iterations,

0:07:05.820,0:07:09.833
in fact, we'll find the prime with[br]high probability. So in expectation, one would

0:07:09.833,0:07:14.771
expect a few hundred iterations and no[br]more. Now that we understand

0:07:14.771,0:07:19.314
Fermat's theorem, the next thing I want[br]to talk about is what's called the

0:07:19.314,0:07:23.915
structure of ZP star. So here, we are[br]going to move 100 years into the future...

0:07:23.915,0:07:28.576
Into the eighteenth century and look at[br]the work of Euler. And one of the first

0:07:28.576,0:07:33.118
things Euler showed is in modern language[br]is that ZP star is what's called a

0:07:33.118,0:07:38.014
cyclic group. What does it mean that ZP[br]star is a cyclic group? What it means is

0:07:38.014,0:07:42.734
that there exists some element G in ZP[br]star, such that if we take G and raise to

0:07:42.734,0:07:47.681
a bunch of powers G, G squared, G cubed, G[br]to the fourth. And so on and so forth up

0:07:47.681,0:07:52.590
until we reach G to the P minus two.[br]Notice there's no point of going beyond G

0:07:52.590,0:07:57.296
to the p minus two, because G to the p[br]minus one by Fermat's theorem is equal to

0:07:57.296,0:08:02.178
one, so then we will cycle back to one. If[br]we go back to G to the p minus one, then G

0:08:02.178,0:08:06.825
to the p will be equal to G, G to the p[br]plus one will be equal to G squared, and

0:08:06.825,0:08:11.825
so on and so forth. So we'll actually get[br]a cycle if we keep raising to higher and

0:08:11.825,0:08:16.590
higher powers of G. So we might as well[br]stop at the power of G to the p minus two.

0:08:16.590,0:08:21.413
And what Euler showed is that in fact[br]there is an element G such that if you

0:08:21.413,0:08:26.300
look at all of its powers all of its[br]powers expand the entire group ZP Star.

0:08:26.300,0:08:31.239
The powers of G give us all the elements[br]in ZP star. Elements of this, of this type

0:08:31.239,0:08:35.997
is called a generator. So G would be said[br]to be a generator of ZP star. So let's

0:08:35.997,0:08:40.696
look at a quick example. So let's look,[br]for example, at P equals seven. And let's

0:08:40.696,0:08:45.575
look at all the powers of three. So three[br]squared three cubed, three to the fourth,

0:08:45.575,0:08:50.130
three to the fifth, Three to the six,[br]already we know, is equal to one modular

0:08:50.130,0:08:54.917
seven by Fermat's Theorem. So there's no[br]point in looking at three to the six. We

0:08:54.917,0:08:59.644
know we would just get one. So here, I[br]calculated all these powers for you, and I

0:08:59.644,0:09:04.431
wrote them out. And you see that in fact,[br]we get all the numbers [inaudible] in Z,

0:09:04.431,0:09:09.313
in Z7 star. In other words, we get[br]one, two, three, four, five, and six. So

0:09:09.313,0:09:14.599
we would say that three is a generator of[br]Z7 star. Now I should point out that not

0:09:14.599,0:09:19.886
every element is a generator. For example,[br]if we look at all the powers of two, well,

0:09:19.886,0:09:24.914
that's not gonna generate the entire[br]group. In particular, if we look at two to

0:09:24.914,0:09:29.650
the zero, we get one. Two to the one, we[br]get two. Two squared is four, and two

0:09:29.650,0:09:34.455
cubed is eight, which is one modular[br]seven. So we cycled back and then two to

0:09:34.455,0:09:39.766
the fourth would be two, two to the fifth[br]would be four. And so on and so forth. So

0:09:39.766,0:09:44.697
if we look at the powers of two, we just[br]get one, two, and four. We don't get the

0:09:44.697,0:09:49.981
whole group and therefore we say that two[br]is not a generator of Z7 star. Now again,

0:09:49.981,0:09:55.831
something that we'll use very often is[br]given an element G of ZP*, if we look at a

0:09:55.831,0:10:01.901
set of all powers of G, the resulting set[br]is gonna be called the group generated by

0:10:01.901,0:10:06.947
G, okay? So these are all the powers of G.[br]They give us what's called a

0:10:06.947,0:10:12.798
multiplicative group. Again, the technical[br]term doesn't matter. The point is we're

0:10:12.798,0:10:18.397
gonna call all these powers of G, the[br]group generated by G. In fact there's this

0:10:18.397,0:10:23.570
notation which I don't use very often,[br]angle G angle, to denote this group that's

0:10:23.570,0:10:30.010
generated by G. And then we call the order[br]of G in Z p star, we simply let that be

0:10:30.010,0:10:35.663
the size of the group that's generated by[br]G. So in other words, the order of G in Z

0:10:35.663,0:10:40.626
p star is the size of this group. But[br]another way to think about that is

0:10:40.626,0:10:46.280
basically it's the smallest integer A such[br]that G to the A is equal to one in Z P.

0:10:47.380,0:10:52.838
Okay, it's basically the smallest power[br]that causes the power of G to be equal to

0:10:52.838,0:10:58.566
one. And it's very easy to see that this[br]equality here basically if we look at all

0:10:58.566,0:11:04.024
the powers of G and we look at one, G, G[br]squared, G cubed and so on and so forth up

0:11:04.024,0:11:09.887
until we get to G to the order of G minus[br]one. And then if we look at the order of G

0:11:09.887,0:11:15.420
to the order of G. This thing is simply[br]going to be equal to one, by definition.

0:11:16.080,0:11:22.000
Okay, so there's no point in looking at[br]any higher powers. We might as well just

0:11:22.000,0:11:27.631
stop raising to powers here. And as a[br]result the size of the set, in fact, is

0:11:27.631,0:11:33.263
the order of G. And you can see that the[br]order is the smallest power such that

0:11:33.263,0:11:38.931
raising G to that power gives us one in Z[br]p. So I hope this is clear although it

0:11:38.931,0:11:43.455
might take a little bit of thinking to[br]absorb all this notation. But in the

0:11:43.455,0:11:48.100
meantime let's look at a few examples. So,[br]again, let's fix our, our prime to be

0:11:48.100,0:11:52.986
seven. And let's look at the order of the[br]number of elements. So what is the order

0:11:52.986,0:11:57.752
of three modulus of seven? Well, we're[br]asking what is the size of the group that

0:11:57.752,0:12:02.759
three generates modulus of seven? Well, we[br]said that three is a generator of Z7 star.

0:12:02.759,0:12:07.705
So it generates all of Z7 star. There are[br]six elements in Z7 star. And therefore we

0:12:07.705,0:12:12.758
say that the order of three is equal to[br]six. Similarly, I can ask, well, what is

0:12:12.758,0:12:17.421
the order of two modulo seven? And in[br]fact, we already saw the answer. So let's,

0:12:17.421,0:12:22.084
I'll ask you, what is the order of two[br]modulo seven and see if you can f igure

0:12:22.084,0:12:28.549
out what this answer is. So the answer is[br]three and again, the reason is if we look

0:12:28.549,0:12:33.618
at the set of powers of two modulo seven,[br]we have one, two, two squared, and then

0:12:33.618,0:12:39.077
two cubed is already equal to one. So this[br]is the entire set of powers of two modulo

0:12:39.077,0:12:44.211
seven. There are only three of them and,[br]therefore, the order of two modulo seven

0:12:44.211,0:12:49.215
is exactly three. Now let me ask you a[br]trick question. What's the order of one

0:12:49.215,0:12:54.499
modulo seven? Well, the answer is one.[br]Because if you look at the group that's

0:12:54.499,0:12:58.633
generated by one, well, there's only one[br]number in that group, namely the number

0:12:58.633,0:13:02.608
one. If I raise one to a whole bunch of[br]powers, I'm always gonna get one, And

0:13:02.608,0:13:07.060
therefore the order of 1 modulo 7[br]In fact the order of 1 modulo any prime

0:13:07.060,0:13:12.518
is always gonna be 1. Now there's an[br]important theorem of Lagrange, that

0:13:12.518,0:13:17.137
actually this is a very, very special case[br]of it, what I am stating here. But

0:13:17.137,0:13:22.309
Langrage's theorem basically implies that[br]if you look at the order of G modulo p,

0:13:22.309,0:13:27.112
the order is always going to divide P-1. So in our two example you see,

0:13:27.297,0:13:32.100
six divides seven minus one, six divides[br]six, and similarly, three divides seven

0:13:32.100,0:13:37.026
minus one. Namely again three divides six.[br]But this is very general; your order is

0:13:37.026,0:13:41.333
always going be a factor of P minus one.[br]In fact, I'll tell you, maybe it's a

0:13:41.333,0:13:45.177
puzzle for you to think about. It's[br]actually very easy to deduce Fermat's

0:13:45.177,0:13:49.179
theorem directly from this fact, from this[br]Lagrange's theorem in fact. And so

0:13:49.179,0:13:53.340
Fermat's theorem really in some sense[br]follows directly from Lagrange's theorem.

0:13:54.580,0:13:59.375
Lagrange, by the way, did his work in the[br]nineteenth century, so you can already see

0:13:59.375,0:14:04.053
how we're making progress through time. We[br]started in Greek times, and already we

0:14:04.053,0:14:09.376
ended up in the nineteenth century. And I[br]can tell you that more advanced crypto

0:14:09.376,0:14:14.024
actually uses twentieth century math very[br]extensively. Now that we understand the

0:14:14.024,0:14:18.416
structure of ZP star, let's generalize[br]that to composites, and look at the

0:14:18.416,0:14:23.471
structure of ZN star. So what I wanna show[br]you here is what's called Euler's Theorem

0:14:23.471,0:14:28.044
which is a, a direct generalization of[br]Fermat's Theorem. So, Euler defined the

0:14:28.044,0:14:32.978
following function. So given an integer N,[br]he defined what's called the phi

0:14:32.978,0:14:37.190
function, phi of M, to be[br]basically the size of the set ZN star.

0:14:37.190,0:14:42.686
This is sometimes called, Euler's phi[br]function. The size of the set Z N star. So

0:14:42.686,0:14:48.521
for example, we already looked at Z twelve[br]star. We said that Z twelve star contains

0:14:48.521,0:14:53.881
these four elements, one, five, seven, and[br]eleven. And therefore we say that phi of

0:14:53.881,0:14:59.310
twelve is simply the number four. So let[br]me ask you as a puzzle, what is phi of P?

0:14:59.310,0:15:06.266
It will basically be the size of Z P star.[br]And so, in fact, we said that in the Z P

0:15:06.266,0:15:12.335
star contains all of Z P except for the[br]number zero. And therefore, phi of P for

0:15:12.335,0:15:18.533
any prime P is gonna be P minus one. Now,[br]there is a special case, which I'm gonna

0:15:18.533,0:15:23.282
state here and we're gonna use later for[br]the RSA system. If N happens to be a

0:15:23.282,0:15:28.277
product of two primes, then phi of N is[br]simply N minus P minus Q plus one. And let

0:15:28.277,0:15:33.045
me just show you why that's true. So[br]basically N is the size of Z N. And now we

0:15:33.045,0:15:37.838
need to remove all the elements that are[br]not relatively prime to m. Well how can an

0:15:37.838,0:15:42.632
element not be relatively prime to m? It's[br]gotta be divisible by p or it's gotta be

0:15:42.632,0:15:47.079
divisible by q. Well how many elements[br]between zero and m minus one are there,

0:15:47.079,0:15:51.757
there that are divisible by p? Well there[br]are exactly q of them. How many elements

0:15:51.757,0:15:55.973
are there that are divisible by q. Well[br]there are exactly p of them. So we

0:15:55.973,0:16:00.593
subtract p to get rid of those divisible[br]by q. We subtract q to get rid of those

0:16:00.593,0:16:05.776
divisible by p. And you notice we[br]subtracted zero twice, because zero is

0:16:05.776,0:16:12.020
divisible both by P and Q. And therefore,[br]we add one just to make sure we subtract

0:16:12.020,0:16:18.264
zero only once. And so it's not difficult[br]to see that phi(N) is N-P-Q+1. And another way

0:16:18.264,0:16:24.599
of writing that is simply (P-1) times (Q-1). Okay,[br]so this is a fact that we will use later

0:16:24.599,0:16:30.275
on, when we come back and talk about the[br]RSA system. So far, this is just defining

0:16:30.275,0:16:35.690
this phi function of Euler. But now Euler[br]put this phi function to really good use.

0:16:35.690,0:16:41.104
And what he proved is this amazing fact[br]here that basically says that if you give

0:16:41.104,0:16:46.060
me any element X in Z N star. In fact, and[br]it so happens that X to the power of phi(N)

0:16:46.060,0:16:50.678
is equal to one in Z N. So you can see[br]that this is a generalization of Fermat's

0:16:50.678,0:16:55.239
theorem; in particular, Fermat's theorem[br]only applied to primes. For primes we know

0:16:55.239,0:16:59.913
that phi(p) is equal to p minus one, and[br]in other words if N were prime we would

0:16:59.913,0:17:04.494
simply write p minus one here, and then we[br]would get exactly Fermat's theorem. The

0:17:04.494,0:17:08.892
beauty of Euler's theorem is that it[br]applies to composites, and not just

0:17:08.892,0:17:16.462
primes. So let's look at some examples. So[br]let's look at five to the power of phi(12).

0:17:16.462,0:17:21.743
So five is an element of Z12 star.[br]If we raise it to the power of five of

0:17:21.743,0:17:27.155
twelve, we should be getting one. Well, we[br]know that phi(12) is 4, so we're

0:17:27.155,0:17:32.037
raising 5 to the power of 4. Five to[br]the power of four is 625 and it's a simple

0:17:32.037,0:17:36.227
calculation to show that that's equal to[br]1 modulo 12. So this is proof

0:17:36.227,0:17:40.468
by example but of course it's not a proof[br]at all. It's just an example. But in fact

0:17:40.468,0:17:44.555
it's not difficult to prove Euler's[br]theorem and in fact I'll tell you that

0:17:44.555,0:17:48.900
Euler's theorem is also a very special[br]case of Lagrange's general theorem.

0:17:49.880,0:17:53.888
Okay so we say that this is a[br]generalization of Fermat's theorem and

0:17:53.888,0:17:58.230
in fact as we'll see this Euler's[br]theorem is the basis of the RSA crypto

0:17:58.230,0:18:03.922
system. So I stop here and we continue[br]with modular quadratic equations in the

0:18:03.922,0:18:04.740
next segment.