[Script Info]
Title: 
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:00.00,0:00:04.22,Default,,0000,0000,0000,,In the previous segment we talked about\Nmodular inversion and we said the Euclid's
Dialogue: 0,0:00:04.22,0:00:08.24,Default,,0000,0000,0000,,algorithm gives us an efficient way to\Nfind the inverse of an element modulo N.
Dialogue: 0,0:00:08.24,0:00:12.26,Default,,0000,0000,0000,,In this segment we're going to forward\Nthrough time and we're going to move to
Dialogue: 0,0:00:12.26,0:00:15.87,Default,,0000,0000,0000,,the seventeenth and eighteenth century\Nwhere we're going to talk about
Dialogue: 0,0:00:15.87,0:00:19.99,Default,,0000,0000,0000,,Fermat and Euler contributions.\NBefore that let's do a quick review of
Dialogue: 0,0:00:19.99,0:00:24.26,Default,,0000,0000,0000,,what we discussed in the previous segment.\NSo as usual I'm going to let N denote the
Dialogue: 0,0:00:24.26,0:00:28.43,Default,,0000,0000,0000,,positive integer and let's just say that N\Nhappens to be a n-bit integer, in other
Dialogue: 0,0:00:28.43,0:00:32.44,Default,,0000,0000,0000,,words it's between two to the n and two to\Nthe n+1, as usual we're going to let P
Dialogue: 0,0:00:32.44,0:00:36.76,Default,,0000,0000,0000,,denote a prime. Now we said that\NZN is a set of integers from zero
Dialogue: 0,0:00:36.76,0:00:41.37,Default,,0000,0000,0000,,to N-1 and we said that we can add and\Nmultiply elements in the set modulo N. We
Dialogue: 0,0:00:41.37,0:00:46.19,Default,,0000,0000,0000,,also said that ZN star is basically the\Nset of invertible elements in ZN. And we
Dialogue: 0,0:00:46.19,0:00:51.24,Default,,0000,0000,0000,,proved a simple lemma to say that, X is\Ninvertible if and only if X is relatively
Dialogue: 0,0:00:51.24,0:00:55.88,Default,,0000,0000,0000,,prime to N. And not only did we\Ncompletely understand which elements are
Dialogue: 0,0:00:55.88,0:01:00.64,Default,,0000,0000,0000,,invertible and which aren't, we also\Nshowed a very efficient algorithm based on
Dialogue: 0,0:01:00.64,0:01:05.57,Default,,0000,0000,0000,,Euclid's extended algorithm, to find the\Ninverse of an element X in ZN. And we said
Dialogue: 0,0:01:05.57,0:01:10.39,Default,,0000,0000,0000,,that the running time of this algorithm,\Nis basically order n squared, where
Dialogue: 0,0:01:10.39,0:01:16.11,Default,,0000,0000,0000,,again, n is the number of bits of the\Nnumber capital N. So as I said, now
Dialogue: 0,0:01:16.11,0:01:21.04,Default,,0000,0000,0000,,we're going to move from Greek times all\Nthe way to the seventeenth century and
Dialogue: 0,0:01:21.04,0:01:26.28,Default,,0000,0000,0000,,talk about Fermat. So Fermat did a number\Nof important theorems. The one that I want
Dialogue: 0,0:01:26.28,0:01:31.21,Default,,0000,0000,0000,,to show you here today is the following.\NSo suppose I give you a prime P. Then in
Dialogue: 0,0:01:31.21,0:01:36.26,Default,,0000,0000,0000,,fact for any element X in ZP star, it so\Nhappens that if I look at X and raise it
Dialogue: 0,0:01:36.26,0:01:41.13,Default,,0000,0000,0000,,to the power of P - 1, I'm a gonna get\None, in ZP. So let's look at a quick
Dialogue: 0,0:01:41.13,0:01:46.06,Default,,0000,0000,0000,,example. Suppose I set the number P to be\Nfive. And I look at, three to the power of
Dialogue: 0,0:01:46.06,0:01:50.64,Default,,0000,0000,0000,,P-1. In other words, three to the power of\Nfour, Three to the power of four is 81,
Dialogue: 0,0:01:50.64,0:01:55.29,Default,,0000,0000,0000,,which in fact, is one modulo five. This\Nexample satisfies Fermat's theorem.
Dialogue: 0,0:01:55.29,0:01:59.52,Default,,0000,0000,0000,,Interestingly, Fermat actually didn't prove this theorem himself. The proof
Dialogue: 0,0:01:59.52,0:02:04.34,Default,,0000,0000,0000,,actually waited until Euler, who\Nproved that almost 100 years later. And in
Dialogue: 0,0:02:04.34,0:02:09.12,Default,,0000,0000,0000,,fact, he proved a much more general\Nversion of this theorem. So let's look at
Dialogue: 0,0:02:09.12,0:02:14.15,Default,,0000,0000,0000,,a simple application of Fermat's theorem.\NSuppose I look at an element X in Z P
Dialogue: 0,0:02:14.15,0:02:19.44,Default,,0000,0000,0000,,star. And I want to remind you here that P\N[inaudible] must be a prime. Well, then what do we
Dialogue: 0,0:02:19.44,0:02:24.66,Default,,0000,0000,0000,,know? We know that X to the P minus one is\Nequal to one. Well, we can write X to the
Dialogue: 0,0:02:24.66,0:02:29.57,Default,,0000,0000,0000,,P minus one as X times X to the power of P\Nminus two. Well so now we know that X
Dialogue: 0,0:02:29.57,0:02:34.09,Default,,0000,0000,0000,,times X to the power of P minus two\Nhappens to be equal to one. And what that
Dialogue: 0,0:02:34.09,0:02:39.31,Default,,0000,0000,0000,,says, is that really the inverse of X\Nmodulo P, is simply X to the P minus two.
Dialogue: 0,0:02:39.31,0:02:44.04,Default,,0000,0000,0000,,So this gives us another algorithm for\Nfinding the inverse of X modulo a prime.
Dialogue: 0,0:02:44.04,0:02:48.84,Default,,0000,0000,0000,,Simply raise X to the power of p minus\Ntwo, and that will give us the inverse of
Dialogue: 0,0:02:48.84,0:02:53.51,Default,,0000,0000,0000,,x. It turns out, actually this is a fine\Nway to compute inverses modulo a prime.
Dialogue: 0,0:02:53.51,0:02:58.30,Default,,0000,0000,0000,,But it has two deficiencies compared to\NEuclid's algorithm. First of all, it only
Dialogue: 0,0:02:58.30,0:03:02.53,Default,,0000,0000,0000,,works modulo primes, Whereas, Euclid's\Nalgorithm worked modulo composites as
Dialogue: 0,0:03:02.53,0:03:07.02,Default,,0000,0000,0000,,well. And second of all, it turns out this\Nalgorithm is actually less efficient. When
Dialogue: 0,0:03:07.02,0:03:10.91,Default,,0000,0000,0000,,we talk about how to do modular\Nexponentiations--we're gonna do that in
Dialogue: 0,0:03:10.91,0:03:15.34,Default,,0000,0000,0000,,the last segment in this module--you'll\Nsee that the running time to compute this
Dialogue: 0,0:03:15.34,0:03:19.79,Default,,0000,0000,0000,,exponentiation is actually cubic in the\Nsize of P. So this will take roughly log
Dialogue: 0,0:03:19.79,0:03:24.27,Default,,0000,0000,0000,,cube of P, whereas if you remember,\NEuclid's algorithm was able to compute the
Dialogue: 0,0:03:24.27,0:03:30.34,Default,,0000,0000,0000,,inverse in quadratic time in the\Nrepresentation of P. So not only is this
Dialogue: 0,0:03:30.34,0:03:36.51,Default,,0000,0000,0000,,algorithm less general it only works for\Nprimes, it's also less efficient. So score
Dialogue: 0,0:03:36.51,0:03:41.47,Default,,0000,0000,0000,,one for Euclid. But nevertheless, this\Nfact about primes is extremely important,
Dialogue: 0,0:03:41.47,0:03:47.51,Default,,0000,0000,0000,,and we're gonna be making extensive use of\Nit in the next couple of weeks. So let me
Dialogue: 0,0:03:47.51,0:03:52.16,Default,,0000,0000,0000,,show you a quick and simple application\Nfor Fermat's theorem suppose we wanted
Dialogue: 0,0:03:52.16,0:03:57.23,Default,,0000,0000,0000,,to generate a large random prime, say our\Nprime needed to be 1,000 bits or so. So
Dialogue: 0,0:03:57.23,0:04:02.01,Default,,0000,0000,0000,,the prime we're looking for is on the\Norder of two to the 1024 [inaudible]. So here's
Dialogue: 0,0:04:02.01,0:04:06.72,Default,,0000,0000,0000,,a very simple probabilistic algorithm.\NWhat we would do is we would choose a
Dialogue: 0,0:04:06.72,0:04:11.94,Default,,0000,0000,0000,,random integer in the interval that was\Nspecified. And then we would test whether
Dialogue: 0,0:04:12.12,0:04:17.15,Default,,0000,0000,0000,,this integer satisfies Fermat's theorem.\NIn other words, we would test for example
Dialogue: 0,0:04:17.15,0:04:22.37,Default,,0000,0000,0000,,using the base two; we would test whether\Ntwo to the power of p minus one equals one
Dialogue: 0,0:04:22.37,0:04:27.27,Default,,0000,0000,0000,,in Z p. If the answer is no, then if this\Nequality doesn't hold, then we know for
Dialogue: 0,0:04:27.27,0:04:33.00,Default,,0000,0000,0000,,sure that the number p that we chose is\Nnot a prime. And if that happens, all we
Dialogue: 0,0:04:33.00,0:04:37.28,Default,,0000,0000,0000,,do is we go back to step one and we try\Nanother prime. And we do this again and
Dialogue: 0,0:04:37.28,0:04:41.78,Default,,0000,0000,0000,,again and again, until finally we find an\Ninteger that satisfies this condition. And
Dialogue: 0,0:04:41.78,0:04:46.01,Default,,0000,0000,0000,,once we find an integer that satisfies\Nthis condition, we simply output it and
Dialogue: 0,0:04:46.01,0:04:51.57,Default,,0000,0000,0000,,stop. Now it turns out, this is actually a\Nfairly difficult statement to prove. But
Dialogue: 0,0:04:51.57,0:04:56.30,Default,,0000,0000,0000,,it turns out if a random number passes\Nthis test, then it's extremely likely to
Dialogue: 0,0:04:56.30,0:05:01.40,Default,,0000,0000,0000,,be a prime. In particular the probability\Nthat P is not a prime is very small. It's
Dialogue: 0,0:05:01.40,0:05:06.19,Default,,0000,0000,0000,,like less than two to the -60 for the\Nrange of 1024 bit numbers. As the
Dialogue: 0,0:05:06.19,0:05:10.74,Default,,0000,0000,0000,,number gets bigger and bigger the\Nprobability that it passes this test here,
Dialogue: 0,0:05:10.74,0:05:15.72,Default,,0000,0000,0000,,but is not a prime drops to zero very\Nquickly. So this is actually quite an
Dialogue: 0,0:05:15.72,0:05:20.46,Default,,0000,0000,0000,,interesting algorithm. You realize we're\Nnot guaranteed that the output is in fact
Dialogue: 0,0:05:20.46,0:05:25.02,Default,,0000,0000,0000,,a prime. All we know is that it's very,\Nvery likely to be a prime. In other words
Dialogue: 0,0:05:25.02,0:05:29.59,Default,,0000,0000,0000,,the only way that it's not a prime is that\Nwe got extremely unlucky. In fact so
Dialogue: 0,0:05:29.59,0:05:34.30,Default,,0000,0000,0000,,unlucky that a negligible probability\Nevent just happened. Another way to say
Dialogue: 0,0:05:34.30,0:05:40.23,Default,,0000,0000,0000,,this is that if you look at the set of all\N1024 integers, then, well, there's the set
Dialogue: 0,0:05:40.23,0:05:45.23,Default,,0000,0000,0000,,of primes. Let me write prime here. And\Nthen there is a small number of
Dialogue: 0,0:05:45.23,0:05:50.80,Default,,0000,0000,0000,,composites. That actually will falsify the\Ntest. Let's call them F for false primes.
Dialogue: 0,0:05:50.80,0:05:55.65,Default,,0000,0000,0000,,Let's call them FP, for false primes.\NThere's a very small number of composites
Dialogue: 0,0:05:55.65,0:06:00.63,Default,,0000,0000,0000,,that are not prime and yet will pass this\Ntest. But as we choose random integers,
Dialogue: 0,0:06:00.63,0:06:05.35,Default,,0000,0000,0000,,you know, we choose one here, one here,\None here, and so on, as we choose random
Dialogue: 0,0:06:05.35,0:06:10.26,Default,,0000,0000,0000,,integers, the probability that we fall\Ninto the set of false primes is so small
Dialogue: 0,0:06:10.26,0:06:15.08,Default,,0000,0000,0000,,That it's essentially a negligible event\Nthat we can ignore. In other words, one
Dialogue: 0,0:06:15.08,0:06:20.59,Default,,0000,0000,0000,,can prove that the set of false primes is\Nextremely small, and a random choice is
Dialogue: 0,0:06:20.59,0:06:25.27,Default,,0000,0000,0000,,unlikely to pick such a false prime. Now I\Nshould mention, in fact, this is a very
Dialogue: 0,0:06:25.27,0:06:28.96,Default,,0000,0000,0000,,simple algorithm for generating primes.\NIt's actually, by far, not the best
Dialogue: 0,0:06:28.96,0:06:32.65,Default,,0000,0000,0000,,algorithm. We have much better algorithms\Nnow. And, in fact, once you have a
Dialogue: 0,0:06:32.65,0:06:36.35,Default,,0000,0000,0000,,candidate prime, we now have very\Nefficient algorithms that will actually
Dialogue: 0,0:06:36.35,0:06:40.50,Default,,0000,0000,0000,,prove beyond a doubt that this candidate\Nprime really is a prime. So we don't even
Dialogue: 0,0:06:40.50,0:06:44.60,Default,,0000,0000,0000,,have to rely on probabilistic statements.\NBut nevertheless, this Fermat test is so
Dialogue: 0,0:06:44.60,0:06:48.60,Default,,0000,0000,0000,,simple, that I just wanted to show you\Nthat it's an easy way to generate primes.
Dialogue: 0,0:06:48.60,0:06:53.08,Default,,0000,0000,0000,,Although in reality, this is not how\Nprimes are generated. As the last point,
Dialogue: 0,0:06:53.08,0:06:57.47,Default,,0000,0000,0000,,I'll say that you might be wondering how\Nmany times this iteration has to repeat
Dialogue: 0,0:06:57.47,0:07:01.54,Default,,0000,0000,0000,,until we actually find the prime. And\Nthat's actually a classic result; it's
Dialogue: 0,0:07:01.54,0:07:05.82,Default,,0000,0000,0000,,called the prime number theorem, which\Nsays that, after a few hundred iterations,
Dialogue: 0,0:07:05.82,0:07:09.83,Default,,0000,0000,0000,,in fact, we'll find the prime with\Nhigh probability. So in expectation, one would
Dialogue: 0,0:07:09.83,0:07:14.77,Default,,0000,0000,0000,,expect a few hundred iterations and no\Nmore. Now that we understand
Dialogue: 0,0:07:14.77,0:07:19.31,Default,,0000,0000,0000,,Fermat's theorem, the next thing I want\Nto talk about is what's called the
Dialogue: 0,0:07:19.31,0:07:23.92,Default,,0000,0000,0000,,structure of ZP star. So here, we are\Ngoing to move 100 years into the future...
Dialogue: 0,0:07:23.92,0:07:28.58,Default,,0000,0000,0000,,Into the eighteenth century and look at\Nthe work of Euler. And one of the first
Dialogue: 0,0:07:28.58,0:07:33.12,Default,,0000,0000,0000,,things Euler showed is in modern language\Nis that ZP star is what's called a
Dialogue: 0,0:07:33.12,0:07:38.01,Default,,0000,0000,0000,,cyclic group. What does it mean that ZP\Nstar is a cyclic group? What it means is
Dialogue: 0,0:07:38.01,0:07:42.73,Default,,0000,0000,0000,,that there exists some element G in ZP\Nstar, such that if we take G and raise to
Dialogue: 0,0:07:42.73,0:07:47.68,Default,,0000,0000,0000,,a bunch of powers G, G squared, G cubed, G\Nto the fourth. And so on and so forth up
Dialogue: 0,0:07:47.68,0:07:52.59,Default,,0000,0000,0000,,until we reach G to the P minus two.\NNotice there's no point of going beyond G
Dialogue: 0,0:07:52.59,0:07:57.30,Default,,0000,0000,0000,,to the p minus two, because G to the p\Nminus one by Fermat's theorem is equal to
Dialogue: 0,0:07:57.30,0:08:02.18,Default,,0000,0000,0000,,one, so then we will cycle back to one. If\Nwe go back to G to the p minus one, then G
Dialogue: 0,0:08:02.18,0:08:06.82,Default,,0000,0000,0000,,to the p will be equal to G, G to the p\Nplus one will be equal to G squared, and
Dialogue: 0,0:08:06.82,0:08:11.82,Default,,0000,0000,0000,,so on and so forth. So we'll actually get\Na cycle if we keep raising to higher and
Dialogue: 0,0:08:11.82,0:08:16.59,Default,,0000,0000,0000,,higher powers of G. So we might as well\Nstop at the power of G to the p minus two.
Dialogue: 0,0:08:16.59,0:08:21.41,Default,,0000,0000,0000,,And what Euler showed is that in fact\Nthere is an element G such that if you
Dialogue: 0,0:08:21.41,0:08:26.30,Default,,0000,0000,0000,,look at all of its powers all of its\Npowers expand the entire group ZP Star.
Dialogue: 0,0:08:26.30,0:08:31.24,Default,,0000,0000,0000,,The powers of G give us all the elements\Nin ZP star. Elements of this, of this type
Dialogue: 0,0:08:31.24,0:08:35.100,Default,,0000,0000,0000,,is called a generator. So G would be said\Nto be a generator of ZP star. So let's
Dialogue: 0,0:08:35.100,0:08:40.70,Default,,0000,0000,0000,,look at a quick example. So let's look,\Nfor example, at P equals seven. And let's
Dialogue: 0,0:08:40.70,0:08:45.58,Default,,0000,0000,0000,,look at all the powers of three. So three\Nsquared three cubed, three to the fourth,
Dialogue: 0,0:08:45.58,0:08:50.13,Default,,0000,0000,0000,,three to the fifth, Three to the six,\Nalready we know, is equal to one modular
Dialogue: 0,0:08:50.13,0:08:54.92,Default,,0000,0000,0000,,seven by Fermat's Theorem. So there's no\Npoint in looking at three to the six. We
Dialogue: 0,0:08:54.92,0:08:59.64,Default,,0000,0000,0000,,know we would just get one. So here, I\Ncalculated all these powers for you, and I
Dialogue: 0,0:08:59.64,0:09:04.43,Default,,0000,0000,0000,,wrote them out. And you see that in fact,\Nwe get all the numbers [inaudible] in Z,
Dialogue: 0,0:09:04.43,0:09:09.31,Default,,0000,0000,0000,,in Z7 star. In other words, we get\None, two, three, four, five, and six. So
Dialogue: 0,0:09:09.31,0:09:14.60,Default,,0000,0000,0000,,we would say that three is a generator of\NZ7 star. Now I should point out that not
Dialogue: 0,0:09:14.60,0:09:19.89,Default,,0000,0000,0000,,every element is a generator. For example,\Nif we look at all the powers of two, well,
Dialogue: 0,0:09:19.89,0:09:24.91,Default,,0000,0000,0000,,that's not gonna generate the entire\Ngroup. In particular, if we look at two to
Dialogue: 0,0:09:24.91,0:09:29.65,Default,,0000,0000,0000,,the zero, we get one. Two to the one, we\Nget two. Two squared is four, and two
Dialogue: 0,0:09:29.65,0:09:34.46,Default,,0000,0000,0000,,cubed is eight, which is one modular\Nseven. So we cycled back and then two to
Dialogue: 0,0:09:34.46,0:09:39.77,Default,,0000,0000,0000,,the fourth would be two, two to the fifth\Nwould be four. And so on and so forth. So
Dialogue: 0,0:09:39.77,0:09:44.70,Default,,0000,0000,0000,,if we look at the powers of two, we just\Nget one, two, and four. We don't get the
Dialogue: 0,0:09:44.70,0:09:49.98,Default,,0000,0000,0000,,whole group and therefore we say that two\Nis not a generator of Z7 star. Now again,
Dialogue: 0,0:09:49.98,0:09:55.83,Default,,0000,0000,0000,,something that we'll use very often is\Ngiven an element G of ZP*, if we look at a
Dialogue: 0,0:09:55.83,0:10:01.90,Default,,0000,0000,0000,,set of all powers of G, the resulting set\Nis gonna be called the group generated by
Dialogue: 0,0:10:01.90,0:10:06.95,Default,,0000,0000,0000,,G, okay? So these are all the powers of G.\NThey give us what's called a
Dialogue: 0,0:10:06.95,0:10:12.80,Default,,0000,0000,0000,,multiplicative group. Again, the technical\Nterm doesn't matter. The point is we're
Dialogue: 0,0:10:12.80,0:10:18.40,Default,,0000,0000,0000,,gonna call all these powers of G, the\Ngroup generated by G. In fact there's this
Dialogue: 0,0:10:18.40,0:10:23.57,Default,,0000,0000,0000,,notation which I don't use very often,\Nangle G angle, to denote this group that's
Dialogue: 0,0:10:23.57,0:10:30.01,Default,,0000,0000,0000,,generated by G. And then we call the order\Nof G in Z p star, we simply let that be
Dialogue: 0,0:10:30.01,0:10:35.66,Default,,0000,0000,0000,,the size of the group that's generated by\NG. So in other words, the order of G in Z
Dialogue: 0,0:10:35.66,0:10:40.63,Default,,0000,0000,0000,,p star is the size of this group. But\Nanother way to think about that is
Dialogue: 0,0:10:40.63,0:10:46.28,Default,,0000,0000,0000,,basically it's the smallest integer A such\Nthat G to the A is equal to one in Z P.
Dialogue: 0,0:10:47.38,0:10:52.84,Default,,0000,0000,0000,,Okay, it's basically the smallest power\Nthat causes the power of G to be equal to
Dialogue: 0,0:10:52.84,0:10:58.57,Default,,0000,0000,0000,,one. And it's very easy to see that this\Nequality here basically if we look at all
Dialogue: 0,0:10:58.57,0:11:04.02,Default,,0000,0000,0000,,the powers of G and we look at one, G, G\Nsquared, G cubed and so on and so forth up
Dialogue: 0,0:11:04.02,0:11:09.89,Default,,0000,0000,0000,,until we get to G to the order of G minus\None. And then if we look at the order of G
Dialogue: 0,0:11:09.89,0:11:15.42,Default,,0000,0000,0000,,to the order of G. This thing is simply\Ngoing to be equal to one, by definition.
Dialogue: 0,0:11:16.08,0:11:22.00,Default,,0000,0000,0000,,Okay, so there's no point in looking at\Nany higher powers. We might as well just
Dialogue: 0,0:11:22.00,0:11:27.63,Default,,0000,0000,0000,,stop raising to powers here. And as a\Nresult the size of the set, in fact, is
Dialogue: 0,0:11:27.63,0:11:33.26,Default,,0000,0000,0000,,the order of G. And you can see that the\Norder is the smallest power such that
Dialogue: 0,0:11:33.26,0:11:38.93,Default,,0000,0000,0000,,raising G to that power gives us one in Z\Np. So I hope this is clear although it
Dialogue: 0,0:11:38.93,0:11:43.46,Default,,0000,0000,0000,,might take a little bit of thinking to\Nabsorb all this notation. But in the
Dialogue: 0,0:11:43.46,0:11:48.10,Default,,0000,0000,0000,,meantime let's look at a few examples. So,\Nagain, let's fix our, our prime to be
Dialogue: 0,0:11:48.10,0:11:52.99,Default,,0000,0000,0000,,seven. And let's look at the order of the\Nnumber of elements. So what is the order
Dialogue: 0,0:11:52.99,0:11:57.75,Default,,0000,0000,0000,,of three modulus of seven? Well, we're\Nasking what is the size of the group that
Dialogue: 0,0:11:57.75,0:12:02.76,Default,,0000,0000,0000,,three generates modulus of seven? Well, we\Nsaid that three is a generator of Z7 star.
Dialogue: 0,0:12:02.76,0:12:07.70,Default,,0000,0000,0000,,So it generates all of Z7 star. There are\Nsix elements in Z7 star. And therefore we
Dialogue: 0,0:12:07.70,0:12:12.76,Default,,0000,0000,0000,,say that the order of three is equal to\Nsix. Similarly, I can ask, well, what is
Dialogue: 0,0:12:12.76,0:12:17.42,Default,,0000,0000,0000,,the order of two modulo seven? And in\Nfact, we already saw the answer. So let's,
Dialogue: 0,0:12:17.42,0:12:22.08,Default,,0000,0000,0000,,I'll ask you, what is the order of two\Nmodulo seven and see if you can f igure
Dialogue: 0,0:12:22.08,0:12:28.55,Default,,0000,0000,0000,,out what this answer is. So the answer is\Nthree and again, the reason is if we look
Dialogue: 0,0:12:28.55,0:12:33.62,Default,,0000,0000,0000,,at the set of powers of two modulo seven,\Nwe have one, two, two squared, and then
Dialogue: 0,0:12:33.62,0:12:39.08,Default,,0000,0000,0000,,two cubed is already equal to one. So this\Nis the entire set of powers of two modulo
Dialogue: 0,0:12:39.08,0:12:44.21,Default,,0000,0000,0000,,seven. There are only three of them and,\Ntherefore, the order of two modulo seven
Dialogue: 0,0:12:44.21,0:12:49.22,Default,,0000,0000,0000,,is exactly three. Now let me ask you a\Ntrick question. What's the order of one
Dialogue: 0,0:12:49.22,0:12:54.50,Default,,0000,0000,0000,,modulo seven? Well, the answer is one.\NBecause if you look at the group that's
Dialogue: 0,0:12:54.50,0:12:58.63,Default,,0000,0000,0000,,generated by one, well, there's only one\Nnumber in that group, namely the number
Dialogue: 0,0:12:58.63,0:13:02.61,Default,,0000,0000,0000,,one. If I raise one to a whole bunch of\Npowers, I'm always gonna get one, And
Dialogue: 0,0:13:02.61,0:13:07.06,Default,,0000,0000,0000,,therefore the order of 1 modulo 7\NIn fact the order of 1 modulo any prime
Dialogue: 0,0:13:07.06,0:13:12.52,Default,,0000,0000,0000,,is always gonna be 1. Now there's an\Nimportant theorem of Lagrange, that
Dialogue: 0,0:13:12.52,0:13:17.14,Default,,0000,0000,0000,,actually this is a very, very special case\Nof it, what I am stating here. But
Dialogue: 0,0:13:17.14,0:13:22.31,Default,,0000,0000,0000,,Langrage's theorem basically implies that\Nif you look at the order of G modulo p,
Dialogue: 0,0:13:22.31,0:13:27.11,Default,,0000,0000,0000,,the order is always going to divide P-1. So in our two example you see,
Dialogue: 0,0:13:27.30,0:13:32.10,Default,,0000,0000,0000,,six divides seven minus one, six divides\Nsix, and similarly, three divides seven
Dialogue: 0,0:13:32.10,0:13:37.03,Default,,0000,0000,0000,,minus one. Namely again three divides six.\NBut this is very general; your order is
Dialogue: 0,0:13:37.03,0:13:41.33,Default,,0000,0000,0000,,always going be a factor of P minus one.\NIn fact, I'll tell you, maybe it's a
Dialogue: 0,0:13:41.33,0:13:45.18,Default,,0000,0000,0000,,puzzle for you to think about. It's\Nactually very easy to deduce Fermat's
Dialogue: 0,0:13:45.18,0:13:49.18,Default,,0000,0000,0000,,theorem directly from this fact, from this\NLagrange's theorem in fact. And so
Dialogue: 0,0:13:49.18,0:13:53.34,Default,,0000,0000,0000,,Fermat's theorem really in some sense\Nfollows directly from Lagrange's theorem.
Dialogue: 0,0:13:54.58,0:13:59.38,Default,,0000,0000,0000,,Lagrange, by the way, did his work in the\Nnineteenth century, so you can already see
Dialogue: 0,0:13:59.38,0:14:04.05,Default,,0000,0000,0000,,how we're making progress through time. We\Nstarted in Greek times, and already we
Dialogue: 0,0:14:04.05,0:14:09.38,Default,,0000,0000,0000,,ended up in the nineteenth century. And I\Ncan tell you that more advanced crypto
Dialogue: 0,0:14:09.38,0:14:14.02,Default,,0000,0000,0000,,actually uses twentieth century math very\Nextensively. Now that we understand the
Dialogue: 0,0:14:14.02,0:14:18.42,Default,,0000,0000,0000,,structure of ZP star, let's generalize\Nthat to composites, and look at the
Dialogue: 0,0:14:18.42,0:14:23.47,Default,,0000,0000,0000,,structure of ZN star. So what I wanna show\Nyou here is what's called Euler's Theorem
Dialogue: 0,0:14:23.47,0:14:28.04,Default,,0000,0000,0000,,which is a, a direct generalization of\NFermat's Theorem. So, Euler defined the
Dialogue: 0,0:14:28.04,0:14:32.98,Default,,0000,0000,0000,,following function. So given an integer N,\Nhe defined what's called the phi
Dialogue: 0,0:14:32.98,0:14:37.19,Default,,0000,0000,0000,,function, phi of M, to be\Nbasically the size of the set ZN star.
Dialogue: 0,0:14:37.19,0:14:42.69,Default,,0000,0000,0000,,This is sometimes called, Euler's phi\Nfunction. The size of the set Z N star. So
Dialogue: 0,0:14:42.69,0:14:48.52,Default,,0000,0000,0000,,for example, we already looked at Z twelve\Nstar. We said that Z twelve star contains
Dialogue: 0,0:14:48.52,0:14:53.88,Default,,0000,0000,0000,,these four elements, one, five, seven, and\Neleven. And therefore we say that phi of
Dialogue: 0,0:14:53.88,0:14:59.31,Default,,0000,0000,0000,,twelve is simply the number four. So let\Nme ask you as a puzzle, what is phi of P?
Dialogue: 0,0:14:59.31,0:15:06.27,Default,,0000,0000,0000,,It will basically be the size of Z P star.\NAnd so, in fact, we said that in the Z P
Dialogue: 0,0:15:06.27,0:15:12.34,Default,,0000,0000,0000,,star contains all of Z P except for the\Nnumber zero. And therefore, phi of P for
Dialogue: 0,0:15:12.34,0:15:18.53,Default,,0000,0000,0000,,any prime P is gonna be P minus one. Now,\Nthere is a special case, which I'm gonna
Dialogue: 0,0:15:18.53,0:15:23.28,Default,,0000,0000,0000,,state here and we're gonna use later for\Nthe RSA system. If N happens to be a
Dialogue: 0,0:15:23.28,0:15:28.28,Default,,0000,0000,0000,,product of two primes, then phi of N is\Nsimply N minus P minus Q plus one. And let
Dialogue: 0,0:15:28.28,0:15:33.04,Default,,0000,0000,0000,,me just show you why that's true. So\Nbasically N is the size of Z N. And now we
Dialogue: 0,0:15:33.04,0:15:37.84,Default,,0000,0000,0000,,need to remove all the elements that are\Nnot relatively prime to m. Well how can an
Dialogue: 0,0:15:37.84,0:15:42.63,Default,,0000,0000,0000,,element not be relatively prime to m? It's\Ngotta be divisible by p or it's gotta be
Dialogue: 0,0:15:42.63,0:15:47.08,Default,,0000,0000,0000,,divisible by q. Well how many elements\Nbetween zero and m minus one are there,
Dialogue: 0,0:15:47.08,0:15:51.76,Default,,0000,0000,0000,,there that are divisible by p? Well there\Nare exactly q of them. How many elements
Dialogue: 0,0:15:51.76,0:15:55.97,Default,,0000,0000,0000,,are there that are divisible by q. Well\Nthere are exactly p of them. So we
Dialogue: 0,0:15:55.97,0:16:00.59,Default,,0000,0000,0000,,subtract p to get rid of those divisible\Nby q. We subtract q to get rid of those
Dialogue: 0,0:16:00.59,0:16:05.78,Default,,0000,0000,0000,,divisible by p. And you notice we\Nsubtracted zero twice, because zero is
Dialogue: 0,0:16:05.78,0:16:12.02,Default,,0000,0000,0000,,divisible both by P and Q. And therefore,\Nwe add one just to make sure we subtract
Dialogue: 0,0:16:12.02,0:16:18.26,Default,,0000,0000,0000,,zero only once. And so it's not difficult\Nto see that phi(N) is N-P-Q+1. And another way
Dialogue: 0,0:16:18.26,0:16:24.60,Default,,0000,0000,0000,,of writing that is simply (P-1) times (Q-1). Okay,\Nso this is a fact that we will use later
Dialogue: 0,0:16:24.60,0:16:30.28,Default,,0000,0000,0000,,on, when we come back and talk about the\NRSA system. So far, this is just defining
Dialogue: 0,0:16:30.28,0:16:35.69,Default,,0000,0000,0000,,this phi function of Euler. But now Euler\Nput this phi function to really good use.
Dialogue: 0,0:16:35.69,0:16:41.10,Default,,0000,0000,0000,,And what he proved is this amazing fact\Nhere that basically says that if you give
Dialogue: 0,0:16:41.10,0:16:46.06,Default,,0000,0000,0000,,me any element X in Z N star. In fact, and\Nit so happens that X to the power of phi(N)
Dialogue: 0,0:16:46.06,0:16:50.68,Default,,0000,0000,0000,,is equal to one in Z N. So you can see\Nthat this is a generalization of Fermat's
Dialogue: 0,0:16:50.68,0:16:55.24,Default,,0000,0000,0000,,theorem; in particular, Fermat's theorem\Nonly applied to primes. For primes we know
Dialogue: 0,0:16:55.24,0:16:59.91,Default,,0000,0000,0000,,that phi(p) is equal to p minus one, and\Nin other words if N were prime we would
Dialogue: 0,0:16:59.91,0:17:04.49,Default,,0000,0000,0000,,simply write p minus one here, and then we\Nwould get exactly Fermat's theorem. The
Dialogue: 0,0:17:04.49,0:17:08.89,Default,,0000,0000,0000,,beauty of Euler's theorem is that it\Napplies to composites, and not just
Dialogue: 0,0:17:08.89,0:17:16.46,Default,,0000,0000,0000,,primes. So let's look at some examples. So\Nlet's look at five to the power of phi(12).
Dialogue: 0,0:17:16.46,0:17:21.74,Default,,0000,0000,0000,,So five is an element of Z12 star.\NIf we raise it to the power of five of
Dialogue: 0,0:17:21.74,0:17:27.16,Default,,0000,0000,0000,,twelve, we should be getting one. Well, we\Nknow that phi(12) is 4, so we're
Dialogue: 0,0:17:27.16,0:17:32.04,Default,,0000,0000,0000,,raising 5 to the power of 4. Five to\Nthe power of four is 625 and it's a simple
Dialogue: 0,0:17:32.04,0:17:36.23,Default,,0000,0000,0000,,calculation to show that that's equal to\N1 modulo 12. So this is proof
Dialogue: 0,0:17:36.23,0:17:40.47,Default,,0000,0000,0000,,by example but of course it's not a proof\Nat all. It's just an example. But in fact
Dialogue: 0,0:17:40.47,0:17:44.56,Default,,0000,0000,0000,,it's not difficult to prove Euler's\Ntheorem and in fact I'll tell you that
Dialogue: 0,0:17:44.56,0:17:48.90,Default,,0000,0000,0000,,Euler's theorem is also a very special\Ncase of Lagrange's general theorem.
Dialogue: 0,0:17:49.88,0:17:53.89,Default,,0000,0000,0000,,Okay so we say that this is a\Ngeneralization of Fermat's theorem and
Dialogue: 0,0:17:53.89,0:17:58.23,Default,,0000,0000,0000,,in fact as we'll see this Euler's\Ntheorem is the basis of the RSA crypto
Dialogue: 0,0:17:58.23,0:18:03.92,Default,,0000,0000,0000,,system. So I stop here and we continue\Nwith modular quadratic equations in the
Dialogue: 0,0:18:03.92,0:18:04.74,Default,,0000,0000,0000,,next segment.