WEBVTT 00:00:00.529 --> 00:00:03.121 In the previous segment, we talked about modulo inversion, 00:00:03.121 --> 00:00:04.927 and we said that Euclid's algorithm gives us 00:00:04.927 --> 00:00:08.905 an efficient method to find the inverse of an element modulo m. 00:00:08.905 --> 00:00:11.266 In this segment we are going to forward through time 00:00:11.266 --> 00:00:15.059 and we're going to move to the 17th and 18th century 00:00:15.059 --> 00:00:16.351 and we're going to talk about Fermat's and Euler's contributions. 00:00:16.351 --> 00:00:20.861 Before that, let's do a quick review of what we discussed in the previous segment. 00:00:20.861 --> 00:00:23.820 So as usual, we're going to let N denote a positive integer, 00:00:23.820 --> 00:00:27.081 and let's just say that N happens to be a n-bit integer. 00:00:27.158 --> 00:00:30.219 In other words, it's between 2^n and 2^(n+1). 00:00:30.219 --> 00:00:32.836 As usual we are going to let p denote a prime. 00:00:32.836 --> 00:00:37.523 Now we said that Z sub n is the set of integers from 0 to N - 1. 00:00:37.523 --> 00:00:41.074 And we said that we can add and multiply elements in the set modulo N. 00:00:41.074 --> 00:00:45.682 We also said the Z_N* is basically the set of invertible elements 00:00:45.682 --> 00:00:50.042 in Z_N and we proved the simple lemma to say that x is invertible 00:00:50.042 --> 00:00:52.926 if and only if x is relatively prime to n. 00:00:52.926 --> 00:00:57.401 And not only did we completely understand which elements are invertible 00:00:57.401 --> 00:00:58.425 and which aren't, 00:00:58.425 --> 00:01:02.112 we also showed a very efficient algorithm, based on Euclid's extended algorithm, 00:01:02.112 --> 00:01:05.361 to find the inverse of an element x in Z_N. 00:01:05.361 --> 00:01:09.689 And we said that the running time of this algorithm is basically of order n-squared 00:01:09.689 --> 00:01:13.460 where again n is the number of bits of the number capital N. 00:01:14.460 --> 00:01:18.522 So as I said, now we're gonna move from Greek times all the way to 00:01:18.522 --> 00:01:21.081 the 17th century and talk about Fermat. 00:01:21.081 --> 00:01:23.963 So Fermat stated a number of important theorems. 00:01:23.963 --> 00:01:26.636 The one that I want to show you here is the following: 00:01:26.636 --> 00:01:28.993 So suppose I give you a prime "p". 00:01:28.993 --> 00:01:33.121 Then in fact, for any element x in in Z_p*, it so happens 00:01:33.121 --> 00:01:36.849 that if I look at x and raise it to the power p-1, 00:01:36.849 --> 00:01:38.951 I'm gonna get 1 in Z_p. 00:01:38.951 --> 00:01:41.831 So let's look at a quick example. 00:01:41.831 --> 00:01:44.110 Suppose I set the number p to be 5 00:01:44.110 --> 00:01:50.238 and I look at 3 to the power of p-1 - in other words 3 to the power of 4 - 00:01:50.238 --> 00:01:53.619 3^4 is 81, which in fact is 1 modulo 5. 00:01:53.619 --> 00:01:56.791 The example satisfies Fermat's theorem. 00:01:56.791 --> 00:02:00.049 Interestingly Fermat actually didn't prove this theorem himself. 00:02:00.049 --> 00:02:04.765 The proof actually waited until Euler, who proved it almost a 100 years later 00:02:04.765 --> 00:02:07.383 and in fact he proved a much more general version of this theorem. 00:02:08.690 --> 00:02:10.845 So lets look at a simple application of Fermat's theorem. 00:02:11.249 --> 00:02:14.312 Suppose I look at an element x in Z_p*, 00:02:14.312 --> 00:02:17.502 and I want to remind you here that p must be a prime. 00:02:17.502 --> 00:02:21.847 Well, then what do we know? We know that x^(p-1) = 1. 00:02:21.909 --> 00:02:27.895 Well, we can write x^(p-1) as x*x^(p-2). 00:02:27.895 --> 00:02:32.900 Well, so now we know that x*x^(p-2) happens to be equal to 1, 00:02:32.900 --> 00:02:37.146 and what that says is that really the inverse of x modulo p 00:02:37.146 --> 00:02:39.438 is simply x^(p-2). 00:02:39.438 --> 00:02:43.923 So this gives us another algorithm for finding the inverse of x modulo a prime: 00:02:43.923 --> 00:02:46.864 simply raise x the power of p-2 00:02:46.864 --> 00:02:48.897 and that will give us the inverse of x. 00:02:48.897 --> 00:02:53.352 It turns out actually this is a fine way to compute inverses modulo a prime, 00:02:53.352 --> 00:02:57.053 but it has 2 deficiencies compared to Euclid's algorithm. 00:02:57.053 --> 00:02:59.511 First of all, it only works modulo primes, 00:02:59.511 --> 00:03:02.725 whereas Euclid's algorithm worked modulo composites as well, 00:03:02.725 --> 00:03:06.238 and second of all it turns out this algorithm is actually less efficient. 00:03:06.238 --> 00:03:09.248 When we talk about how to do modular exponentiation 00:03:09.248 --> 00:03:11.496 - we're gonna do that in the last segment in this module - 00:03:11.496 --> 00:03:14.832 you'll see that the running time to compute this exponentiation 00:03:14.832 --> 00:03:18.122 is actually cubic in the size of p, 00:03:18.122 --> 00:03:20.542 so this will take roughly log^3(p), 00:03:20.542 --> 00:03:22.862 whereas, if you remember, Euclid's algorithm was able 00:03:22.862 --> 00:03:25.228 to compute the inverse in quadratic time 00:03:25.228 --> 00:03:27.166 in the representation of p. 00:03:28.689 --> 00:03:32.013 So not only is this algorithm less general 00:03:32.013 --> 00:03:33.593 - it only works for primes - 00:03:33.593 --> 00:03:36.620 it's also less efficient. 00:03:36.620 --> 00:03:38.257 So score one for Euclid, NOTE Paragraph 00:03:38.257 --> 00:03:42.559 but nevertheless, this fact about primes is extremely important 00:03:42.559 --> 00:03:44.556 and we're going to be making extensive use of it 00:03:44.556 --> 00:03:47.773 in the next couple of weeks. 00:03:47.773 --> 00:03:51.345 So let me show you a quick and simple application of Fermat's theorem. 00:03:51.345 --> 00:03:53.612 Suppose we wanted to generate a large random prime. 00:03:53.612 --> 00:03:57.856 Say our prime needed to be 1000 bits or so. 00:03:57.856 --> 00:04:02.592 So the prime we're looking for is on the order of 2^1024, say. 00:04:02.592 --> 00:04:05.075 So here is a very simple probabilistic algorithm: 00:04:05.075 --> 00:04:07.812 What we would do is, we would choose a random integer 00:04:07.812 --> 00:04:10.542 in the interval that was specified, 00:04:10.542 --> 00:04:15.439 and then we would test whether this integer satisfies Fermat's theorem. 00:04:15.439 --> 00:04:16.608 In other words, we would test - 00:04:16.608 --> 00:04:18.373 for example, using the base 2, 00:04:18.373 --> 00:04:22.931 we would test whether 2^(p-1) equals 1 in Z_p. 00:04:22.931 --> 00:04:26.096 If the answer is no, if this equality doesn't hold, 00:04:26.096 --> 00:04:30.617 then we know for sure that the number p that we chose is not a prime. 00:04:30.617 --> 00:04:34.800 And if that happens, all we do is we go back to step 1 00:04:34.800 --> 00:04:36.207 and we try another prime. 00:04:36.207 --> 00:04:37.747 We do this again and again and again, 00:04:37.747 --> 00:04:41.856 until finally we find an integer that satisfies this condition. 00:04:41.856 --> 00:04:43.911 And once we find an integer that satisfies this condition, 00:04:43.911 --> 00:04:48.032 we simply output it and stop. 00:04:48.032 --> 00:04:49.322 Now it turns out 00:04:49.322 --> 00:04:51.304 - this is actually a fairly difficult statement to prove - 00:04:51.304 --> 00:04:54.838 but it turns out, if a random number passes this test, 00:04:54.838 --> 00:04:57.087 then it's extremely likely to be a prime. 00:04:57.087 --> 00:04:59.625 In particular, the probability that p is not a prime 00:04:59.625 --> 00:05:01.075 is very small. 00:05:01.075 --> 00:05:05.540 It's, like, less than 2^-60 for the range of 1024-bit numbers. 00:05:05.540 --> 00:05:08.075 As the number gets bigger and bigger, 00:05:08.075 --> 00:05:09.607 the probability that it passes this test here, 00:05:09.607 --> 00:05:16.010 but is not a prime, drops to zero very quickly. 00:05:16.010 --> 00:05:17.102 So this is actually quite an interesting algorithm. 00:05:17.102 --> 00:05:21.145 You realize: we're not guaranteed that the output is in fact a prime. 00:05:21.145 --> 00:05:24.006 All we know is that it's very very likely to be a prime. 00:05:24.006 --> 00:05:26.176 In other words: the only way that it's not a prime 00:05:26.176 --> 00:05:28.268 is that we got extremely unlucky. 00:05:28.268 --> 00:05:34.009 In fact, so unlucky that a negligible-probability event just happened. 00:05:34.009 --> 00:05:35.910 Another way to say this is that, 00:05:35.910 --> 00:05:39.370 if you look at the set of all 1024-bit integers, 00:05:39.370 --> 00:05:43.737 then, well, there is the set of primes, when we write "prime" here, 00:05:43.737 --> 00:05:46.360 and then there is a small number of composites 00:05:46.360 --> 00:05:48.334 that actually will falsify the test, 00:05:48.334 --> 00:05:51.072 let's call them F for "false primes". 00:05:51.072 --> 00:05:54.201 Let's call them FP, for "false primes". 00:05:54.201 --> 00:05:56.132 There is a very small number of composites 00:05:56.132 --> 00:05:58.995 that are not prime and yet will pass this test, 00:05:58.995 --> 00:06:01.853 but as we choose random integers 00:06:01.853 --> 00:06:04.660 - you know, we choose one here and one here, and so on - 00:06:04.660 --> 00:06:05.924 as we choose random integers, 00:06:05.924 --> 00:06:09.036 the probability that we fall into this set of false primes 00:06:09.036 --> 00:06:12.952 is so small that it's essentially a negligible event 00:06:12.952 --> 00:06:14.535 that we can ignore. 00:06:14.535 --> 00:06:17.043 In other words, one can prove that the set of false primes 00:06:17.043 --> 00:06:18.534 is extremely small, 00:06:18.534 --> 00:06:24.136 and a random choice is unlikely to pick such a false prime. 00:06:24.136 --> 00:06:24.740 Now I should mention, 00:06:24.740 --> 00:06:27.588 in fact, this is a very simple algorithm for generating primes. 00:06:27.588 --> 00:06:29.789 It's actually by far not the best algorithm. 00:06:29.789 --> 00:06:31.735 We have much better algorithms now. 00:06:31.735 --> 00:06:33.242 And in fact, once you have a candidate prime 00:06:33.242 --> 00:06:35.269 we now have very efficient algorithms 00:06:35.269 --> 00:06:37.069 that will actually prove beyond a doubt 00:06:37.069 --> 00:06:40.328 that this candidate prime really is a prime. 00:06:40.328 --> 00:06:43.003 So we don't even have to rely on probabilistic statements. 00:06:43.003 --> 00:06:43.578 And nevertheless, 00:06:43.578 --> 00:06:44.843 this Fermat test is so simple 00:06:44.843 --> 00:06:46.415 that I just wanted to show you 00:06:46.415 --> 00:06:48.405 that it's an easy way to generate primes 00:06:48.405 --> 00:06:52.075 although in reality this is not how primes are generated. 00:06:52.075 --> 00:06:54.336 As a last point, I'll say that 00:06:54.336 --> 00:06:56.973 you might be wondering how many times this iteration 00:06:56.973 --> 00:07:00.004 has to repeat until we actually find a prime. 00:07:00.004 --> 00:07:01.473 And that's actually a classic result, 00:07:01.473 --> 00:07:02.876 it's called the Prime Number Theorem 00:07:02.876 --> 00:07:03.884 which says that 00:07:03.884 --> 00:07:05.338 after a few hundred iterations 00:07:05.338 --> 00:07:08.675 we'll find a prime with high probability. 00:07:08.675 --> 00:07:10.338 So expectation, one would expect 00:07:10.338 --> 00:07:14.075 a few hundred iterations, no more. 00:07:14.075 --> 00:07:15.930 Now that we understand Fermat's theorem, 00:07:15.930 --> 00:07:17.607 the next thing I want to talk about is 00:07:17.607 --> 00:07:20.213 what's called the structure of (Z_p)*. 00:07:20.213 --> 00:07:22.116 So here we're going to move a hundred years into the future, 00:07:22.116 --> 00:07:23.735 into the 18th century, 00:07:23.735 --> 00:07:25.523 and look at the work of Euler. 00:07:25.523 --> 00:07:27.282 And one of the first things Euler showed 00:07:27.282 --> 00:07:29.328 is, in modern language, 00:07:29.328 --> 00:07:32.810 is that (Z_p)* is what's called a cyclic group. 00:07:32.810 --> 00:07:35.473 So what does it mean that (Z_p)* is a cyclic group? 00:07:35.473 --> 00:07:36.078 What it means is: 00:07:36.078 --> 00:07:39.771 there exists some element g in (Z_p)* 00:07:39.771 --> 00:07:43.368 such that if we take g and raise it to a bunch of powers, 00:07:43.368 --> 00:07:47.098 g, g^2, g^3, g^4 and so on and so forth 00:07:47.098 --> 00:07:50.672 up until we reach g^(p-2) 00:07:50.672 --> 00:07:53.160 - notice there is no point of going beyond g^(p-2) 00:07:53.160 --> 00:07:57.805 because g^(p-1) by Fermat's theorem is equal to 1, 00:07:57.805 --> 00:08:00.208 so then we will cycle back to 1 00:08:00.208 --> 00:08:02.223 if we go back to g^(p-1), 00:08:02.223 --> 00:08:04.651 then g^p will be equal to g, 00:08:04.651 --> 00:08:07.425 g^(p+1) will be equal to g^2, and so on and so forth, 00:08:07.425 --> 00:08:08.598 so we'll actually get a cycle 00:08:08.598 --> 00:08:11.529 if we keep raising to higher and higher powers of g, 00:08:11.529 --> 00:08:17.337 so we might as well stop at the power of g^(p-2). 00:08:17.337 --> 00:08:18.368 And what Euler showed is 00:08:18.368 --> 00:08:20.343 that in fact there is an element g 00:08:20.343 --> 00:08:22.728 such that if we look at all of its powers, 00:08:22.728 --> 00:08:26.934 all of its powers span the entire group (Z_p)*. 00:08:26.934 --> 00:08:30.817 Powers of g give us all the elements in (Z_p)*. 00:08:30.817 --> 00:08:33.335 An element of this type is called a generator. 00:08:33.335 --> 00:08:36.854 So g would be said to be a generator of (Z_p)*. 00:08:36.854 --> 00:08:38.031 So let's look at a quick example. 00:08:38.031 --> 00:08:40.386 Let's look for example at p=7, 00:08:40.386 --> 00:08:43.541 and let's look at all the powers of 3, 00:08:43.541 --> 00:08:47.011 which are 3^2, 3^3, 3^4, 3^5. 00:08:47.011 --> 00:08:51.788 3^6 already, we know, is equal to 1 modulo 7 by Fermat's theorem, 00:08:51.788 --> 00:08:53.869 so there's no point in looking at 3^6: 00:08:53.869 --> 00:08:56.176 we know we would just get 1. 00:08:56.176 --> 00:08:58.077 So here I calculated all of these powers for you, 00:08:58.077 --> 00:08:59.344 and I wrote them out, 00:08:59.344 --> 00:09:03.505 and you see that in fact, we get all the numbers in (Z_7)*. 00:09:03.505 --> 00:09:10.081 In other words, we get 1, 2, 3, 4, 5 and 6. 00:09:10.081 --> 00:09:14.245 So we would say that 3 is a generator of (Z_7)*. 00:09:14.245 --> 00:09:17.212 Now I should point out that not every element is a generator. 00:09:17.212 --> 00:09:20.601 For example, if we look at all the powers of 2, 00:09:20.601 --> 00:09:23.033 well, that's not going to generate the entire group. 00:09:23.033 --> 00:09:25.881 In particular, if we look at 2^0, we get 1. 00:09:25.881 --> 00:09:28.310 2^1, we get 2. 00:09:28.310 --> 00:09:33.804 2^2 is 4, and 2^3 is 8, which is 1 modulo 7. 00:09:33.804 --> 00:09:35.398 So we cycled back. 00:09:35.398 --> 00:09:37.149 And then 2^4 would be 2, 00:09:37.149 --> 00:09:40.196 2^5 would be 4, and so on and so forth. 00:09:40.196 --> 00:09:41.923 So if we look at the powers of 2, 00:09:41.923 --> 00:09:43.951 we just get 1, 2 and 4. 00:09:43.951 --> 00:09:45.133 We don't get the whole group. 00:09:45.133 --> 00:09:49.952 And therefore we say that 2 is not a generator of (Z_7)*. 00:09:49.952 --> 00:09:51.787 Now again, something that we'll use very often 00:09:51.787 --> 00:09:56.198 is, given an element g of (Z_p)*, 00:09:56.198 --> 00:09:59.786 if we look at the set of all powers of g, 00:09:59.786 --> 00:10:01.972 the resulting set is going to be called 00:10:01.972 --> 00:10:04.953 the group generated by g. 00:10:04.953 --> 00:10:07.309 OK? So these are all the powers of g, 00:10:07.309 --> 00:10:10.508 they give us what's called a multiplicative group, 00:10:10.508 --> 00:10:12.000 again, the technical term doesn't matter, 00:10:12.000 --> 00:10:14.705 the point is: we're going to call all these powers of g 00:10:14.705 --> 00:10:17.566 the group generated by g. 00:10:17.566 --> 00:10:20.111 In fact, there's this notation which I don't use very often: 00:10:20.111 --> 00:10:26.210 "" to denote this group that's generated by g. 00:10:26.210 --> 00:10:28.971 And then we call the order of g in (Z_p)*, 00:10:28.971 --> 00:10:30.623 we simply let that be 00:10:30.623 --> 00:10:33.406 the size of the group that's generated by g. 00:10:33.406 --> 00:10:35.982 So in other words, 00:10:35.982 --> 00:10:36.801 the order of g in (Z_p)* 00:10:36.801 --> 00:10:38.680 is the size of this group. 00:10:38.680 --> 00:10:40.139 But another way to think about that 00:10:40.139 --> 00:10:43.299 is basically, it's the smallest integer a 00:10:43.299 --> 00:10:48.170 such that g^a is equal to 1 in Z_p. 00:10:48.170 --> 00:10:50.073 OK? It's basically the smallest power 00:10:50.073 --> 00:10:53.758 that causes a power of g to be equal to 1. 00:10:53.758 --> 00:10:54.487 And it's very easy to see that 00:10:54.487 --> 00:10:55.838 this equality here, 00:10:55.838 --> 00:10:58.825 basically if we look at all the powers of g 00:10:58.825 --> 00:11:03.422 - we look at 1, g, g^2, g^3 and so on and so forth, 00:11:03.422 --> 00:11:07.023 up until we get to g to the order of g minus 1, 00:11:07.023 --> 00:11:10.945 and then if we look at g to the order of g, 00:11:10.945 --> 00:11:14.413 this thing is simply going to be equal to 1 by definition. 00:11:14.463 --> 00:11:16.751 OK? So there's no point in looking into higher powers, 00:11:16.951 --> 00:11:19.305 we might as well just stop raising to powers here. 00:11:19.405 --> 00:11:25.680 And as a result, the size of the set, 00:11:25.680 --> 00:11:29.548 in fact, is the order of g. 00:11:29.548 --> 00:11:32.198 And you can see that the order is the smallest power 00:11:32.198 --> 00:11:34.024 such that raising g to that power 00:11:34.024 --> 00:11:37.584 gives us 1 in Z_p. 00:11:37.584 --> 00:11:38.757 So I hope this is clear, 00:11:38.757 --> 00:11:40.399 although it might take a little lateral thinking 00:11:40.399 --> 00:11:41.910 to absorb all this notation. 00:11:41.910 --> 00:11:44.573 But in the meantime, let's look at a few examples. 00:11:44.573 --> 00:11:48.064 So again, let's fix our prime to be 7. 00:11:48.064 --> 00:11:50.289 And let's look at the order of a number of elements. 00:11:50.289 --> 00:11:52.883 So what is the order of 3 modulo 7? 00:11:52.883 --> 00:11:55.099 Well, we're asking: what is the size of the group 00:11:55.099 --> 00:11:58.153 that 3 generates modulo 7? 00:11:58.153 --> 00:12:01.195 Well, we said that 3 is a generator of (Z_7)*, 00:12:01.195 --> 00:12:03.887 so it generates all of (Z_7)*. 00:12:03.887 --> 00:12:06.478 There are 6 elements in (Z_7)*. 00:12:06.478 --> 00:12:11.572 And therefore we say that the order of 3 is equal to 6. 00:12:11.572 --> 00:12:12.309 Similarly I can ask: 00:12:12.309 --> 00:12:14.667 well, what is the order of 2 modulo 7? 00:12:14.667 --> 00:12:17.295 And in fact, we already saw the answer. 00:12:17.295 --> 00:12:20.669 So, let's - I'll ask you, what is the order of 2 modulo 7 00:12:20.669 --> 00:12:25.437 and see if you can figure out what this answer is. 00:12:25.437 --> 00:12:26.868 So the answer is 3. 00:12:26.868 --> 00:12:27.853 And again, the reason is, 00:12:27.853 --> 00:12:31.662 if we look at the set of powers of 2 modulo 7, 00:12:31.662 --> 00:12:34.376 well, we have 1, 2, 2^2, 00:12:34.376 --> 00:12:36.847 and then 2^3 that's already equal to 1, 00:12:36.847 --> 00:12:40.077 so this is the entire set of powers of 2 modulo 7. 00:12:40.077 --> 00:12:42.472 There are only three of them. 00:12:42.472 --> 00:12:46.295 And therefore, the order of 2 modulo 7 is exactly 3. 00:12:46.295 --> 00:12:47.327 Now let me ask you a trick question: 00:12:47.327 --> 00:12:51.809 What's the order of 1 modulo 7? 00:12:51.809 --> 00:12:52.904 Well, the answer is 1, 00:12:52.904 --> 00:12:55.963 because if you look at the group that's generated by 1, 00:12:55.963 --> 00:12:57.707 well, there's only one number in that group, 00:12:57.707 --> 00:12:58.842 namely the number 1. 00:12:58.842 --> 00:13:00.282 If I raise 1 to a whole bunch of powers, 00:13:00.282 --> 00:13:01.872 I'm always going to get 1, 00:13:01.872 --> 00:13:04.337 and therefore the order of 1 modulo 7, 00:13:04.337 --> 00:13:06.468 in fact, the order of 1 modulo any prime, 00:13:06.468 --> 00:13:10.285 is always going to be 1. 00:13:10.285 --> 00:13:12.276 Now, there's an important theorem of Lagrange that 00:13:12.276 --> 00:13:15.788 - actually, this is a very very special case of what I was telling here. 00:13:15.788 --> 00:13:18.206 But Lagrange's theorem basically implies 00:13:18.206 --> 00:13:20.877 that if you look at the order of g modulo p, 00:13:20.877 --> 00:13:24.173 the order is always going to divide p-1. 00:13:24.173 --> 00:13:26.669 So in our two example[s], you see 00:13:26.669 --> 00:13:30.440 6 divides 7 minus 1. 6 divides 6. 00:13:30.440 --> 00:13:35.206 And similarly, 3 divides 7-1, namely again, 3 divides 6. 00:13:35.206 --> 00:13:36.608 But this is very general. 00:13:36.608 --> 00:13:40.273 The order is always going to be a factor of p-1. 00:13:40.273 --> 00:13:40.882 In fact, I'll tell you, 00:13:40.882 --> 00:13:42.431 maybe it's a puzzle for you to think about 00:13:42.431 --> 00:13:45.249 it's actually very easy to deduce Fermat's theorem 00:13:45.249 --> 00:13:49.152 directly from this fact, from this Lagrange's theorem fact, 00:13:49.152 --> 00:13:50.859 and so Fermat's theorem really in some sense 00:13:50.859 --> 00:13:55.795 follows directly from Lagrange's theorem. 00:13:55.795 --> 00:13:58.452 Lagrange, by the way, did this work in the 19th century, 00:13:58.452 --> 00:14:01.819 so we can already see how we're making progress through time. 00:14:01.819 --> 00:14:03.422 We started in Greek times, 00:14:03.422 --> 00:14:07.777 and already we ended up in the 19th century. 00:14:07.777 --> 00:14:09.246 And I can tell you that more advanced crypto 00:14:09.246 --> 00:14:13.302 actually uses 20th-century math very extensively. 00:14:13.302 --> 00:14:15.635 Now that we understand the structure of (Z_p)*, 00:14:15.635 --> 00:14:17.435 let's generalize that to composites 00:14:17.435 --> 00:14:19.963 and look at the structure of (Z_N)*. 00:14:19.963 --> 00:14:22.755 So what I want to show you here is what's called Euler's theorem, 00:14:22.755 --> 00:14:26.220 which is a direct generalization of Fermat's theorem. 00:14:26.220 --> 00:14:28.552 So Euler defined the following function: 00:14:28.552 --> 00:14:30.403 So given an integer N, 00:14:30.403 --> 00:14:33.573 we define what's called the phi function, phi of N, 00:14:33.573 --> 00:14:37.622 to be basically the size of the set (Z_N)*. 00:14:37.622 --> 00:14:40.225 This is sometimes called "Euler's phi function". 00:14:40.225 --> 00:14:42.786 The size of the set (Z_N)*. 00:14:42.786 --> 00:14:46.063 So for example, we already looked at (Z_12)*. 00:14:46.063 --> 00:14:49.171 We said that (Z_12)* contains these four elements 00:14:49.171 --> 00:14:51.206 1, 5, 7 and 11, 00:14:51.206 --> 00:14:56.014 and therefore we say that phi of 12 is simply the number of 4. 00:14:56.014 --> 00:14:57.214 So let me ask you as a puzzle: 00:14:57.214 --> 00:14:59.294 What is phi of p? 00:14:59.294 --> 00:15:04.071 It'll basically be the size of (Z_P)*. 00:15:04.071 --> 00:15:05.152 And so in fact we said 00:15:05.152 --> 00:15:08.139 that (Z_P)* contains all of Z_P 00:15:08.139 --> 00:15:09.933 except for the number zero, 00:15:09.933 --> 00:15:12.983 and therefore phi of p for any prime p 00:15:12.983 --> 00:15:16.740 is going to be p-1. 00:15:16.740 --> 00:15:18.700 Now there's a special case which I'm going to state here 00:15:18.700 --> 00:15:21.013 we're going to use later for the RSA system: 00:15:21.013 --> 00:15:23.567 if N happens to be a product of two primes, 00:15:23.567 --> 00:15:27.505 then phi of N is simply N minus p minus q plus 1. 00:15:27.505 --> 00:15:29.554 Let me just show you why that's true. 00:15:29.554 --> 00:15:32.435 Basically, N is the size of Z_N. 00:15:32.435 --> 00:15:34.562 And now we need to remove all the elements 00:15:34.562 --> 00:15:37.209 that are not relatively prime to N. 00:15:37.209 --> 00:15:40.015 Well, how can an element not be relatively prime to N? 00:15:40.015 --> 00:15:41.495 It's got to be divisible by p, 00:15:41.495 --> 00:15:43.747 or it's got to be divisible by q. 00:15:43.747 --> 00:15:45.757 Well, how many elements between zero and N-1 00:15:45.757 --> 00:15:48.881 are there that are divisible by p? 00:15:48.881 --> 00:15:50.429 Well, there are exactly q of them. 00:15:50.429 --> 00:15:53.005 How many elements are there that are divisible by q? 00:15:53.005 --> 00:15:54.509 Well, there are exactly p of them. 00:15:54.509 --> 00:15:57.971 So we subtract p to get rid of those divisible by q, 00:15:57.971 --> 00:16:01.104 we subtract q to get rid of those divisible by p. 00:16:01.104 --> 00:16:03.793 And you'll notice we subtracted 0 twice, 00:16:03.793 --> 00:16:07.671 because 0 is divisible both by p and q. 00:16:07.671 --> 00:16:09.246 And therefore we add 1, 00:16:09.246 --> 00:16:12.190 just to make sure we subtract 0 only once. 00:16:12.190 --> 00:16:13.178 And so it's not difficult to see 00:16:13.178 --> 00:16:17.057 that phi of N is N minus p minus q plus 1. 00:16:17.057 --> 00:16:18.371 And another way of writing that is simply: 00:16:18.371 --> 00:16:22.438 p minus 1, times q minus 1. 00:16:22.438 --> 00:16:24.212 OK? So this is a fact that we will use 00:16:24.212 --> 00:16:25.909 later on when we will come back 00:16:25.909 --> 00:16:29.420 and talk about the RSA system. 00:16:29.420 --> 00:16:32.689 So far, this is just defining this phi function of Euler. 00:16:32.689 --> 00:16:35.830 But now, Euler put this phi function to really good use. 00:16:35.830 --> 00:16:38.003 And what he proved is this amazing fact here 00:16:38.003 --> 00:16:39.177 that basically says 00:16:39.177 --> 00:16:43.069 that if you give me any element x in (Z_N)*, 00:16:43.069 --> 00:16:44.576 in fact it so happens that 00:16:44.576 --> 00:16:48.772 x to the power of phi of N is equal to 1 in Z_N. 00:16:48.772 --> 00:16:50.984 So you can see that this is a generalization of Fermat's theorem. 00:16:50.984 --> 00:16:53.994 In particular, Fermat's theorem only applied to primes. 00:16:53.994 --> 00:16:57.337 For primes we know that phi of p is equal to p-1, 00:16:57.337 --> 00:16:57.975 and in other words, 00:16:57.975 --> 00:17:01.336 if N were prime, we would simply write p-1 here, 00:17:01.336 --> 00:17:04.457 and then we would get exactly Fermat's theorem. 00:17:04.457 --> 00:17:06.124 The beauty of Euler's theorem is that 00:17:06.124 --> 00:17:09.252 it applies to composites and not just primes. 00:17:09.706 --> 00:17:13.758 So let's look at some examples: 00:17:13.758 --> 00:17:17.415 So let's look at 5 to the power of phi of 12. 00:17:17.415 --> 00:17:20.438 So 5 is an element of (Z_12)*. 00:17:20.438 --> 00:17:22.712 If we raise it to the power of phi of 12, 00:17:22.712 --> 00:17:24.105 we should be getting 1. 00:17:24.105 --> 00:17:26.477 Well, we know that phi of 12 is 4, 00:17:26.477 --> 00:17:29.801 so we're raising 5 to the power of 4. 00:17:29.801 --> 00:17:31.998 5 to the power of 4 is 625. 00:17:31.998 --> 00:17:33.471 And it's a simple calculation to show that 00:17:33.471 --> 00:17:36.428 that's equal to 1 modulo 12. 00:17:36.428 --> 00:17:37.789 So this is proof by example, 00:17:37.789 --> 00:17:38.955 but of course it's not a proof at all, 00:17:38.955 --> 00:17:40.124 it's just an example. 00:17:40.124 --> 00:17:42.485 And in fact, it's not difficult to prove Euler's theorem. 00:17:42.485 --> 00:17:44.375 And in fact I tell you that Euler's theorem 00:17:44.375 --> 00:17:46.120 is also a very special case 00:17:46.120 --> 00:17:49.366 of Lagrange's general theorem. 00:17:49.366 --> 00:17:51.437 OK. So we said that 00:17:51.437 --> 00:17:53.576 this is a generalization of Fermat's theorem 00:17:53.576 --> 00:17:54.959 and in fact, as we'll see, 00:17:54.959 --> 00:17:56.004 this Euler's theorem 00:17:56.004 --> 00:18:00.205 is the basis of the RSA cryptosystem. 00:18:00.205 --> 00:18:00.950 So I'll stop here, 00:18:00.950 --> 00:18:03.278 and we'll continue with modular quadratic equations 00:18:03.278 --> 99:59:59.999 in the next segment.