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