WEBVTT 00:00:00.000 --> 00:00:04.220 In the previous segment we talked about modular inversion and we said the Euclid's 00:00:04.220 --> 00:00:08.238 algorithm gives us an efficient way to find the inverse of an element modulo N. 00:00:08.238 --> 00:00:12.256 In this segment we're going to forward through time and we're going to move to 00:00:12.256 --> 00:00:15.866 the seventeenth and eighteenth century where we're going to talk about 00:00:15.866 --> 00:00:19.986 Fermat and Euler contributions. Before that let's do a quick review of 00:00:19.986 --> 00:00:24.257 what we discussed in the previous segment. So as usual I'm going to let N denote the 00:00:24.257 --> 00:00:28.427 positive integer and let's just say that N happens to be a n-bit integer, in other 00:00:28.427 --> 00:00:32.445 words it's between two to the n and two to the n+1, as usual we're going to let P 00:00:32.445 --> 00:00:36.761 denote a prime. Now we said that ZN is a set of integers from zero 00:00:36.761 --> 00:00:41.370 to N-1 and we said that we can add and multiply elements in the set modulo N. We 00:00:41.370 --> 00:00:46.186 also said that ZN star is basically the set of invertible elements in ZN. And we 00:00:46.186 --> 00:00:51.243 proved a simple lemma to say that, X is invertible if and only if X is relatively 00:00:51.243 --> 00:00:55.879 prime to N. And not only did we completely understand which elements are 00:00:55.879 --> 00:01:00.635 invertible and which aren't, we also showed a very efficient algorithm based on 00:01:00.635 --> 00:01:05.572 Euclid's extended algorithm, to find the inverse of an element X in ZN. And we said 00:01:05.572 --> 00:01:10.388 that the running time of this algorithm, is basically order n squared, where 00:01:10.388 --> 00:01:16.107 again, n is the number of bits of the number capital N. So as I said, now 00:01:16.107 --> 00:01:21.037 we're going to move from Greek times all the way to the seventeenth century and 00:01:21.037 --> 00:01:26.276 talk about Fermat. So Fermat did a number of important theorems. The one that I want 00:01:26.276 --> 00:01:31.206 to show you here today is the following. So suppose I give you a prime P. Then in 00:01:31.206 --> 00:01:36.260 fact for any element X in ZP star, it so happens that if I look at X and raise it 00:01:36.260 --> 00:01:41.130 to the power of P - 1, I'm a gonna get one, in ZP. So let's look at a quick 00:01:41.130 --> 00:01:46.061 example. Suppose I set the number P to be five. And I look at, three to the power of 00:01:46.061 --> 00:01:50.645 P-1. In other words, three to the power of four, Three to the power of four is 81, 00:01:50.645 --> 00:01:55.286 which in fact, is one modulo five. This example satisfies Fermat's theorem. 00:01:55.286 --> 00:01:59.521 Interestingly, Fermat actually didn't prove this theorem himself. The proof 00:01:59.521 --> 00:02:04.337 actually waited until Euler, who proved that almost 100 years later. And in 00:02:04.337 --> 00:02:09.122 fact, he proved a much more general version of this theorem. So let's look at 00:02:09.122 --> 00:02:14.154 a simple application of Fermat's theorem. Suppose I look at an element X in Z P 00:02:14.154 --> 00:02:19.441 star. And I want to remind you here that P [inaudible] must be a prime. Well, then what do we 00:02:19.441 --> 00:02:24.664 know? We know that X to the P minus one is equal to one. Well, we can write X to the 00:02:24.664 --> 00:02:29.573 P minus one as X times X to the power of P minus two. Well so now we know that X 00:02:29.573 --> 00:02:34.087 times X to the power of P minus two happens to be equal to one. And what that 00:02:34.087 --> 00:02:39.310 says, is that really the inverse of X modulo P, is simply X to the P minus two. 00:02:39.310 --> 00:02:44.042 So this gives us another algorithm for finding the inverse of X modulo a prime. 00:02:44.042 --> 00:02:48.835 Simply raise X to the power of p minus two, and that will give us the inverse of 00:02:48.835 --> 00:02:53.508 x. It turns out, actually this is a fine way to compute inverses modulo a prime. 00:02:53.508 --> 00:02:58.301 But it has two deficiencies compared to Euclid's algorithm. First of all, it only 00:02:58.301 --> 00:03:02.528 works modulo primes, Whereas, Euclid's algorithm worked modulo composites as 00:03:02.528 --> 00:03:07.017 well. And second of all, it turns out this algorithm is actually less efficient. When 00:03:07.017 --> 00:03:10.911 we talk about how to do modular exponentiations--we're gonna do that in 00:03:10.911 --> 00:03:15.345 the last segment in this module--you'll see that the running time to compute this 00:03:15.345 --> 00:03:19.792 exponentiation is actually cubic in the size of P. So this will take roughly log 00:03:19.792 --> 00:03:24.266 cube of P, whereas if you remember, Euclid's algorithm was able to compute the 00:03:24.266 --> 00:03:30.343 inverse in quadratic time in the representation of P. So not only is this 00:03:30.343 --> 00:03:36.512 algorithm less general it only works for primes, it's also less efficient. So score 00:03:36.512 --> 00:03:41.473 one for Euclid. But nevertheless, this fact about primes is extremely important, 00:03:41.473 --> 00:03:47.506 and we're gonna be making extensive use of it in the next couple of weeks. So let me 00:03:47.506 --> 00:03:52.155 show you a quick and simple application for Fermat's theorem suppose we wanted 00:03:52.155 --> 00:03:57.226 to generate a large random prime, say our prime needed to be 1,000 bits or so. So 00:03:57.226 --> 00:04:02.006 the prime we're looking for is on the order of two to the 1024 [inaudible]. So here's 00:04:02.006 --> 00:04:06.724 a very simple probabilistic algorithm. What we would do is we would choose a 00:04:06.724 --> 00:04:11.938 random integer in the interval that was specified. And then we would test whether 00:04:12.124 --> 00:04:17.153 this integer satisfies Fermat's theorem. In other words, we would test for example 00:04:17.153 --> 00:04:22.367 using the base two; we would test whether two to the power of p minus one equals one 00:04:22.367 --> 00:04:27.271 in Z p. If the answer is no, then if this equality doesn't hold, then we know for 00:04:27.271 --> 00:04:33.003 sure that the number p that we chose is not a prime. And if that happens, all we 00:04:33.003 --> 00:04:37.284 do is we go back to step one and we try another prime. And we do this again and 00:04:37.284 --> 00:04:41.782 again and again, until finally we find an integer that satisfies this condition. And 00:04:41.782 --> 00:04:46.009 once we find an integer that satisfies this condition, we simply output it and 00:04:46.009 --> 00:04:51.573 stop. Now it turns out, this is actually a fairly difficult statement to prove. But 00:04:51.573 --> 00:04:56.305 it turns out if a random number passes this test, then it's extremely likely to 00:04:56.305 --> 00:05:01.398 be a prime. In particular the probability that P is not a prime is very small. It's 00:05:01.398 --> 00:05:06.191 like less than two to the -60 for the range of 1024 bit numbers. As the 00:05:06.191 --> 00:05:10.744 number gets bigger and bigger the probability that it passes this test here, 00:05:10.744 --> 00:05:15.716 but is not a prime drops to zero very quickly. So this is actually quite an 00:05:15.716 --> 00:05:20.455 interesting algorithm. You realize we're not guaranteed that the output is in fact 00:05:20.455 --> 00:05:25.021 a prime. All we know is that it's very, very likely to be a prime. In other words 00:05:25.021 --> 00:05:29.587 the only way that it's not a prime is that we got extremely unlucky. In fact so 00:05:29.587 --> 00:05:34.298 unlucky that a negligible probability event just happened. Another way to say 00:05:34.298 --> 00:05:40.230 this is that if you look at the set of all 1024 integers, then, well, there's the set 00:05:40.230 --> 00:05:45.233 of primes. Let me write prime here. And then there is a small number of 00:05:45.233 --> 00:05:50.805 composites. That actually will falsify the test. Let's call them F for false primes. 00:05:50.805 --> 00:05:55.653 Let's call them FP, for false primes. There's a very small number of composites 00:05:55.653 --> 00:06:00.626 that are not prime and yet will pass this test. But as we choose random integers, 00:06:00.626 --> 00:06:05.349 you know, we choose one here, one here, one here, and so on, as we choose random 00:06:05.349 --> 00:06:10.260 integers, the probability that we fall into the set of false primes is so small 00:06:10.260 --> 00:06:15.082 That it's essentially a negligible event that we can ignore. In other words, one 00:06:15.082 --> 00:06:20.591 can prove that the set of false primes is extremely small, and a random choice is 00:06:20.591 --> 00:06:25.266 unlikely to pick such a false prime. Now I should mention, in fact, this is a very 00:06:25.266 --> 00:06:28.960 simple algorithm for generating primes. It's actually, by far, not the best 00:06:28.960 --> 00:06:32.654 algorithm. We have much better algorithms now. And, in fact, once you have a 00:06:32.654 --> 00:06:36.349 candidate prime, we now have very efficient algorithms that will actually 00:06:36.349 --> 00:06:40.498 prove beyond a doubt that this candidate prime really is a prime. So we don't even 00:06:40.498 --> 00:06:44.597 have to rely on probabilistic statements. But nevertheless, this Fermat test is so 00:06:44.597 --> 00:06:48.595 simple, that I just wanted to show you that it's an easy way to generate primes. 00:06:48.595 --> 00:06:53.076 Although in reality, this is not how primes are generated. As the last point, 00:06:53.076 --> 00:06:57.468 I'll say that you might be wondering how many times this iteration has to repeat 00:06:57.468 --> 00:07:01.536 until we actually find the prime. And that's actually a classic result; it's 00:07:01.536 --> 00:07:05.820 called the prime number theorem, which says that, after a few hundred iterations, 00:07:05.820 --> 00:07:09.833 in fact, we'll find the prime with high probability. So in expectation, one would 00:07:09.833 --> 00:07:14.771 expect a few hundred iterations and no more. Now that we understand 00:07:14.771 --> 00:07:19.314 Fermat's theorem, the next thing I want to talk about is what's called the 00:07:19.314 --> 00:07:23.915 structure of ZP star. So here, we are going to move 100 years into the future... 00:07:23.915 --> 00:07:28.576 Into the eighteenth century and look at the work of Euler. And one of the first 00:07:28.576 --> 00:07:33.118 things Euler showed is in modern language is that ZP star is what's called a 00:07:33.118 --> 00:07:38.014 cyclic group. What does it mean that ZP star is a cyclic group? What it means is 00:07:38.014 --> 00:07:42.734 that there exists some element G in ZP star, such that if we take G and raise to 00:07:42.734 --> 00:07:47.681 a bunch of powers G, G squared, G cubed, G to the fourth. And so on and so forth up 00:07:47.681 --> 00:07:52.590 until we reach G to the P minus two. Notice there's no point of going beyond G 00:07:52.590 --> 00:07:57.296 to the p minus two, because G to the p minus one by Fermat's theorem is equal to 00:07:57.296 --> 00:08:02.178 one, so then we will cycle back to one. If we go back to G to the p minus one, then G 00:08:02.178 --> 00:08:06.825 to the p will be equal to G, G to the p plus one will be equal to G squared, and 00:08:06.825 --> 00:08:11.825 so on and so forth. So we'll actually get a cycle if we keep raising to higher and 00:08:11.825 --> 00:08:16.590 higher powers of G. So we might as well stop at the power of G to the p minus two. 00:08:16.590 --> 00:08:21.413 And what Euler showed is that in fact there is an element G such that if you 00:08:21.413 --> 00:08:26.300 look at all of its powers all of its powers expand the entire group ZP Star. 00:08:26.300 --> 00:08:31.239 The powers of G give us all the elements in ZP star. Elements of this, of this type 00:08:31.239 --> 00:08:35.997 is called a generator. So G would be said to be a generator of ZP star. So let's 00:08:35.997 --> 00:08:40.696 look at a quick example. So let's look, for example, at P equals seven. And let's 00:08:40.696 --> 00:08:45.575 look at all the powers of three. So three squared three cubed, three to the fourth, 00:08:45.575 --> 00:08:50.130 three to the fifth, Three to the six, already we know, is equal to one modular 00:08:50.130 --> 00:08:54.917 seven by Fermat's Theorem. So there's no point in looking at three to the six. We 00:08:54.917 --> 00:08:59.644 know we would just get one. So here, I calculated all these powers for you, and I 00:08:59.644 --> 00:09:04.431 wrote them out. And you see that in fact, we get all the numbers [inaudible] in Z, 00:09:04.431 --> 00:09:09.313 in Z7 star. In other words, we get one, two, three, four, five, and six. So 00:09:09.313 --> 00:09:14.599 we would say that three is a generator of Z7 star. Now I should point out that not 00:09:14.599 --> 00:09:19.886 every element is a generator. For example, if we look at all the powers of two, well, 00:09:19.886 --> 00:09:24.914 that's not gonna generate the entire group. In particular, if we look at two to 00:09:24.914 --> 00:09:29.650 the zero, we get one. Two to the one, we get two. Two squared is four, and two 00:09:29.650 --> 00:09:34.455 cubed is eight, which is one modular seven. So we cycled back and then two to 00:09:34.455 --> 00:09:39.766 the fourth would be two, two to the fifth would be four. And so on and so forth. So 00:09:39.766 --> 00:09:44.697 if we look at the powers of two, we just get one, two, and four. We don't get the 00:09:44.697 --> 00:09:49.981 whole group and therefore we say that two is not a generator of Z7 star. Now again, 00:09:49.981 --> 00:09:55.831 something that we'll use very often is given an element G of ZP*, if we look at a 00:09:55.831 --> 00:10:01.901 set of all powers of G, the resulting set is gonna be called the group generated by 00:10:01.901 --> 00:10:06.947 G, okay? So these are all the powers of G. They give us what's called a 00:10:06.947 --> 00:10:12.798 multiplicative group. Again, the technical term doesn't matter. The point is we're 00:10:12.798 --> 00:10:18.397 gonna call all these powers of G, the group generated by G. In fact there's this 00:10:18.397 --> 00:10:23.570 notation which I don't use very often, angle G angle, to denote this group that's 00:10:23.570 --> 00:10:30.010 generated by G. And then we call the order of G in Z p star, we simply let that be 00:10:30.010 --> 00:10:35.663 the size of the group that's generated by G. So in other words, the order of G in Z 00:10:35.663 --> 00:10:40.626 p star is the size of this group. But another way to think about that is 00:10:40.626 --> 00:10:46.280 basically it's the smallest integer A such that G to the A is equal to one in Z P. 00:10:47.380 --> 00:10:52.838 Okay, it's basically the smallest power that causes the power of G to be equal to 00:10:52.838 --> 00:10:58.566 one. And it's very easy to see that this equality here basically if we look at all 00:10:58.566 --> 00:11:04.024 the powers of G and we look at one, G, G squared, G cubed and so on and so forth up 00:11:04.024 --> 00:11:09.887 until we get to G to the order of G minus one. And then if we look at the order of G 00:11:09.887 --> 00:11:15.420 to the order of G. This thing is simply going to be equal to one, by definition. 00:11:16.080 --> 00:11:22.000 Okay, so there's no point in looking at any higher powers. We might as well just 00:11:22.000 --> 00:11:27.631 stop raising to powers here. And as a result the size of the set, in fact, is 00:11:27.631 --> 00:11:33.263 the order of G. And you can see that the order is the smallest power such that 00:11:33.263 --> 00:11:38.931 raising G to that power gives us one in Z p. So I hope this is clear although it 00:11:38.931 --> 00:11:43.455 might take a little bit of thinking to absorb all this notation. But in the 00:11:43.455 --> 00:11:48.100 meantime let's look at a few examples. So, again, let's fix our, our prime to be 00:11:48.100 --> 00:11:52.986 seven. And let's look at the order of the number of elements. So what is the order 00:11:52.986 --> 00:11:57.752 of three modulus of seven? Well, we're asking what is the size of the group that 00:11:57.752 --> 00:12:02.759 three generates modulus of seven? Well, we said that three is a generator of Z7 star. 00:12:02.759 --> 00:12:07.705 So it generates all of Z7 star. There are six elements in Z7 star. And therefore we 00:12:07.705 --> 00:12:12.758 say that the order of three is equal to six. Similarly, I can ask, well, what is 00:12:12.758 --> 00:12:17.421 the order of two modulo seven? And in fact, we already saw the answer. So let's, 00:12:17.421 --> 00:12:22.084 I'll ask you, what is the order of two modulo seven and see if you can f igure 00:12:22.084 --> 00:12:28.549 out what this answer is. So the answer is three and again, the reason is if we look 00:12:28.549 --> 00:12:33.618 at the set of powers of two modulo seven, we have one, two, two squared, and then 00:12:33.618 --> 00:12:39.077 two cubed is already equal to one. So this is the entire set of powers of two modulo 00:12:39.077 --> 00:12:44.211 seven. There are only three of them and, therefore, the order of two modulo seven 00:12:44.211 --> 00:12:49.215 is exactly three. Now let me ask you a trick question. What's the order of one 00:12:49.215 --> 00:12:54.499 modulo seven? Well, the answer is one. Because if you look at the group that's 00:12:54.499 --> 00:12:58.633 generated by one, well, there's only one number in that group, namely the number 00:12:58.633 --> 00:13:02.608 one. If I raise one to a whole bunch of powers, I'm always gonna get one, And 00:13:02.608 --> 00:13:07.060 therefore the order of 1 modulo 7 In fact the order of 1 modulo any prime 00:13:07.060 --> 00:13:12.518 is always gonna be 1. Now there's an important theorem of Lagrange, that 00:13:12.518 --> 00:13:17.137 actually this is a very, very special case of it, what I am stating here. But 00:13:17.137 --> 00:13:22.309 Langrage's theorem basically implies that if you look at the order of G modulo p, 00:13:22.309 --> 00:13:27.112 the order is always going to divide P-1. So in our two example you see, 00:13:27.297 --> 00:13:32.100 six divides seven minus one, six divides six, and similarly, three divides seven 00:13:32.100 --> 00:13:37.026 minus one. Namely again three divides six. But this is very general; your order is 00:13:37.026 --> 00:13:41.333 always going be a factor of P minus one. In fact, I'll tell you, maybe it's a 00:13:41.333 --> 00:13:45.177 puzzle for you to think about. It's actually very easy to deduce Fermat's 00:13:45.177 --> 00:13:49.179 theorem directly from this fact, from this Lagrange's theorem in fact. And so 00:13:49.179 --> 00:13:53.340 Fermat's theorem really in some sense follows directly from Lagrange's theorem. 00:13:54.580 --> 00:13:59.375 Lagrange, by the way, did his work in the nineteenth century, so you can already see 00:13:59.375 --> 00:14:04.053 how we're making progress through time. We started in Greek times, and already we 00:14:04.053 --> 00:14:09.376 ended up in the nineteenth century. And I can tell you that more advanced crypto 00:14:09.376 --> 00:14:14.024 actually uses twentieth century math very extensively. Now that we understand the 00:14:14.024 --> 00:14:18.416 structure of ZP star, let's generalize that to composites, and look at the 00:14:18.416 --> 00:14:23.471 structure of ZN star. So what I wanna show you here is what's called Euler's Theorem 00:14:23.471 --> 00:14:28.044 which is a, a direct generalization of Fermat's Theorem. So, Euler defined the 00:14:28.044 --> 00:14:32.978 following function. So given an integer N, he defined what's called the phi 00:14:32.978 --> 00:14:37.190 function, phi of M, to be basically the size of the set ZN star. 00:14:37.190 --> 00:14:42.686 This is sometimes called, Euler's phi function. The size of the set Z N star. So 00:14:42.686 --> 00:14:48.521 for example, we already looked at Z twelve star. We said that Z twelve star contains 00:14:48.521 --> 00:14:53.881 these four elements, one, five, seven, and eleven. And therefore we say that phi of 00:14:53.881 --> 00:14:59.310 twelve is simply the number four. So let me ask you as a puzzle, what is phi of P? 00:14:59.310 --> 00:15:06.266 It will basically be the size of Z P star. And so, in fact, we said that in the Z P 00:15:06.266 --> 00:15:12.335 star contains all of Z P except for the number zero. And therefore, phi of P for 00:15:12.335 --> 00:15:18.533 any prime P is gonna be P minus one. Now, there is a special case, which I'm gonna 00:15:18.533 --> 00:15:23.282 state here and we're gonna use later for the RSA system. If N happens to be a 00:15:23.282 --> 00:15:28.277 product of two primes, then phi of N is simply N minus P minus Q plus one. And let 00:15:28.277 --> 00:15:33.045 me just show you why that's true. So basically N is the size of Z N. And now we 00:15:33.045 --> 00:15:37.838 need to remove all the elements that are not relatively prime to m. Well how can an 00:15:37.838 --> 00:15:42.632 element not be relatively prime to m? It's gotta be divisible by p or it's gotta be 00:15:42.632 --> 00:15:47.079 divisible by q. Well how many elements between zero and m minus one are there, 00:15:47.079 --> 00:15:51.757 there that are divisible by p? Well there are exactly q of them. How many elements 00:15:51.757 --> 00:15:55.973 are there that are divisible by q. Well there are exactly p of them. So we 00:15:55.973 --> 00:16:00.593 subtract p to get rid of those divisible by q. We subtract q to get rid of those 00:16:00.593 --> 00:16:05.776 divisible by p. And you notice we subtracted zero twice, because zero is 00:16:05.776 --> 00:16:12.020 divisible both by P and Q. And therefore, we add one just to make sure we subtract 00:16:12.020 --> 00:16:18.264 zero only once. And so it's not difficult to see that phi(N) is N-P-Q+1. And another way 00:16:18.264 --> 00:16:24.599 of writing that is simply (P-1) times (Q-1). Okay, so this is a fact that we will use later 00:16:24.599 --> 00:16:30.275 on, when we come back and talk about the RSA system. So far, this is just defining 00:16:30.275 --> 00:16:35.690 this phi function of Euler. But now Euler put this phi function to really good use. 00:16:35.690 --> 00:16:41.104 And what he proved is this amazing fact here that basically says that if you give 00:16:41.104 --> 00:16:46.060 me any element X in Z N star. In fact, and it so happens that X to the power of phi(N) 00:16:46.060 --> 00:16:50.678 is equal to one in Z N. So you can see that this is a generalization of Fermat's 00:16:50.678 --> 00:16:55.239 theorem; in particular, Fermat's theorem only applied to primes. For primes we know 00:16:55.239 --> 00:16:59.913 that phi(p) is equal to p minus one, and in other words if N were prime we would 00:16:59.913 --> 00:17:04.494 simply write p minus one here, and then we would get exactly Fermat's theorem. The 00:17:04.494 --> 00:17:08.892 beauty of Euler's theorem is that it applies to composites, and not just 00:17:08.892 --> 00:17:16.462 primes. So let's look at some examples. So let's look at five to the power of phi(12). 00:17:16.462 --> 00:17:21.743 So five is an element of Z12 star. If we raise it to the power of five of 00:17:21.743 --> 00:17:27.155 twelve, we should be getting one. Well, we know that phi(12) is 4, so we're 00:17:27.155 --> 00:17:32.037 raising 5 to the power of 4. Five to the power of four is 625 and it's a simple 00:17:32.037 --> 00:17:36.227 calculation to show that that's equal to 1 modulo 12. So this is proof 00:17:36.227 --> 00:17:40.468 by example but of course it's not a proof at all. It's just an example. But in fact 00:17:40.468 --> 00:17:44.555 it's not difficult to prove Euler's theorem and in fact I'll tell you that 00:17:44.555 --> 00:17:48.900 Euler's theorem is also a very special case of Lagrange's general theorem. 00:17:49.880 --> 00:17:53.888 Okay so we say that this is a generalization of Fermat's theorem and 00:17:53.888 --> 00:17:58.230 in fact as we'll see this Euler's theorem is the basis of the RSA crypto 00:17:58.230 --> 00:18:03.922 system. So I stop here and we continue with modular quadratic equations in the 00:18:03.922 --> 00:18:04.740 next segment.