1 00:00:00,529 --> 00:00:03,121 In the previous segment, we talked about modulo inversion, 2 00:00:03,121 --> 00:00:04,927 and we said that Euclid's algorithm gives us 3 00:00:04,927 --> 00:00:08,905 an efficient method to find the inverse of an element modulo m. 4 00:00:08,905 --> 00:00:11,266 In this segment we are going to forward through time 5 00:00:11,266 --> 00:00:15,059 and we're going to move to the 17th and 18th century 6 00:00:15,059 --> 00:00:16,351 and we're going to talk about Fermat's and Euler's contributions. 7 00:00:16,351 --> 00:00:20,861 Before that, let's do a quick review of what we discussed in the previous segment. 8 00:00:20,861 --> 00:00:23,820 So as usual, we're going to let N denote a positive integer, 9 00:00:23,820 --> 00:00:27,081 and let's just say that N happens to be a n-bit integer. 10 00:00:27,158 --> 00:00:30,219 In other words, it's between 2^n and 2^(n+1). 11 00:00:30,219 --> 00:00:32,836 As usual we are going to let p denote a prime. 12 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. 13 00:00:37,523 --> 00:00:41,074 And we said that we can add and multiply elements in the set modulo N. 14 00:00:41,074 --> 00:00:45,682 We also said the Z_N* is basically the set of invertible elements 15 00:00:45,682 --> 00:00:50,042 in Z_N and we proved the simple lemma to say that x is invertible 16 00:00:50,042 --> 00:00:52,926 if and only if x is relatively prime to n. 17 00:00:52,926 --> 00:00:57,401 And not only did we completely understand which elements are invertible 18 00:00:57,401 --> 00:00:58,425 and which aren't, 19 00:00:58,425 --> 00:01:02,112 we also showed a very efficient algorithm, based on Euclid's extended algorithm, 20 00:01:02,112 --> 00:01:05,361 to find the inverse of an element x in Z_N. 21 00:01:05,361 --> 00:01:09,689 And we said that the running time of this algorithm is basically of order n-squared 22 00:01:09,689 --> 00:01:13,460 where again n is the number of bits of the number capital N. 23 00:01:14,460 --> 00:01:18,522 So as I said, now we're gonna move from Greek times all the way to 24 00:01:18,522 --> 00:01:21,081 the 17th century and talk about Fermat. 25 00:01:21,081 --> 00:01:23,963 So Fermat stated a number of important theorems. 26 00:01:23,963 --> 00:01:26,636 The one that I want to show you here is the following: 27 00:01:26,636 --> 00:01:28,993 So suppose I give you a prime "p". 28 00:01:28,993 --> 00:01:33,121 Then in fact, for any element x in in Z_p*, it so happens 29 00:01:33,121 --> 00:01:36,849 that if I look at x and raise it to the power p-1, 30 00:01:36,849 --> 00:01:38,951 I'm gonna get 1 in Z_p. 31 00:01:38,951 --> 00:01:41,831 So let's look at a quick example. 32 00:01:41,831 --> 00:01:44,110 Suppose I set the number p to be 5 33 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 - 34 00:01:50,238 --> 00:01:53,619 3^4 is 81, which in fact is 1 modulo 5. 35 00:01:53,619 --> 00:01:56,791 The example satisfies Fermat's theorem. 36 00:01:56,791 --> 00:02:00,049 Interestingly Fermat actually didn't prove this theorem himself. 37 00:02:00,049 --> 00:02:04,765 The proof actually waited until Euler, who proved it almost a 100 years later 38 00:02:04,765 --> 00:02:07,383 and in fact he proved a much more general version of this theorem. 39 00:02:08,690 --> 00:02:10,845 So lets look at a simple application of Fermat's theorem. 40 00:02:11,249 --> 00:02:14,312 Suppose I look at an element x in Z_p*, 41 00:02:14,312 --> 00:02:17,502 and I want to remind you here that p must be a prime. 42 00:02:17,502 --> 00:02:21,847 Well, then what do we know? We know that x^(p-1) = 1. 43 00:02:21,909 --> 00:02:27,895 Well, we can write x^(p-1) as x*x^(p-2). 44 00:02:27,895 --> 00:02:32,900 Well, so now we know that x*x^(p-2) happens to be equal to 1, 45 00:02:32,900 --> 00:02:37,146 and what that says is that really the inverse of x modulo p 46 00:02:37,146 --> 00:02:39,438 is simply x^(p-2). 47 00:02:39,438 --> 00:02:43,923 So this gives us another algorithm for finding the inverse of x modulo a prime: 48 00:02:43,923 --> 00:02:46,864 simply raise x the power of p-2 49 00:02:46,864 --> 00:02:48,897 and that will give us the inverse of x. 50 00:02:48,897 --> 00:02:53,352 It turns out actually this is a fine way to compute inverses modulo a prime, 51 00:02:53,352 --> 00:02:57,053 but it has 2 deficiencies compared to Euclid's algorithm. 52 00:02:57,053 --> 00:02:59,511 First of all, it only works modulo primes, 53 00:02:59,511 --> 00:03:02,725 whereas Euclid's algorithm worked modulo composites as well, 54 00:03:02,725 --> 00:03:06,238 and second of all it turns out this algorithm is actually less efficient. 55 00:03:06,238 --> 00:03:09,248 When we talk about how to do modular exponentiation 56 00:03:09,248 --> 00:03:11,496 - we're gonna do that in the last segment in this module - 57 00:03:11,496 --> 00:03:14,832 you'll see that the running time to compute this exponentiation 58 00:03:14,832 --> 00:03:18,122 is actually cubic in the size of p, 59 00:03:18,122 --> 00:03:20,542 so this will take roughly log^3(p), 60 00:03:20,542 --> 00:03:22,862 whereas, if you remember, Euclid's algorithm was able 61 00:03:22,862 --> 00:03:25,228 to compute the inverse in quadratic time 62 00:03:25,228 --> 00:03:27,166 in the representation of p. 63 00:03:28,689 --> 00:03:32,013 So not only is this algorithm less general 64 00:03:32,013 --> 00:03:33,593 - it only works for primes - 65 00:03:33,593 --> 00:03:36,620 it's also less efficient. 66 00:03:36,620 --> 00:03:38,257 So score one for Euclid, 67 00:03:38,257 --> 00:03:42,559 but nevertheless, this fact about primes is extremely important 68 00:03:42,559 --> 00:03:44,556 and we're going to be making extensive use of it 69 00:03:44,556 --> 00:03:47,773 in the next couple of weeks. 70 00:03:47,773 --> 00:03:51,345 So let me show you a quick and simple application of Fermat's theorem. 71 00:03:51,345 --> 00:03:53,612 Suppose we wanted to generate a large random prime. 72 00:03:53,612 --> 00:03:57,856 Say our prime needed to be 1000 bits or so. 73 00:03:57,856 --> 00:04:02,592 So the prime we're looking for is on the order of 2^1024, say. 74 00:04:02,592 --> 00:04:05,075 So here is a very simple probabilistic algorithm: 75 00:04:05,075 --> 00:04:07,812 What we would do is, we would choose a random integer 76 00:04:07,812 --> 00:04:10,542 in the interval that was specified, 77 00:04:10,542 --> 00:04:15,439 and then we would test whether this integer satisfies Fermat's theorem. 78 00:04:15,439 --> 00:04:16,608 In other words, we would test - 79 00:04:16,608 --> 00:04:18,373 for example, using the base 2, 80 00:04:18,373 --> 00:04:22,931 we would test whether 2^(p-1) equals 1 in Z_p. 81 00:04:22,931 --> 00:04:26,096 If the answer is no, if this equality doesn't hold, 82 00:04:26,096 --> 00:04:30,617 then we know for sure that the number p that we chose is not a prime. 83 00:04:30,617 --> 00:04:34,800 And if that happens, all we do is we go back to step 1 84 00:04:34,800 --> 00:04:36,207 and we try another prime. 85 00:04:36,207 --> 00:04:37,747 We do this again and again and again, 86 00:04:37,747 --> 00:04:41,856 until finally we find an integer that satisfies this condition. 87 00:04:41,856 --> 00:04:43,911 And once we find an integer that satisfies this condition, 88 00:04:43,911 --> 00:04:48,032 we simply output it and stop. 89 00:04:48,032 --> 00:04:49,322 Now it turns out 90 00:04:49,322 --> 00:04:51,304 - this is actually a fairly difficult statement to prove - 91 00:04:51,304 --> 00:04:54,838 but it turns out, if a random number passes this test, 92 00:04:54,838 --> 00:04:57,087 then it's extremely likely to be a prime. 93 00:04:57,087 --> 00:04:59,625 In particular, the probability that p is not a prime 94 00:04:59,625 --> 00:05:01,075 is very small. 95 00:05:01,075 --> 00:05:05,540 It's, like, less than 2^-60 for the range of 1024-bit numbers. 96 00:05:05,540 --> 00:05:08,075 As the number gets bigger and bigger, 97 00:05:08,075 --> 00:05:09,607 the probability that it passes this test here, 98 00:05:09,607 --> 00:05:16,010 but is not a prime, drops to zero very quickly. 99 00:05:16,010 --> 00:05:17,102 So this is actually quite an interesting algorithm. 100 00:05:17,102 --> 00:05:21,145 You realize: we're not guaranteed that the output is in fact a prime. 101 00:05:21,145 --> 00:05:24,006 All we know is that it's very very likely to be a prime. 102 00:05:24,006 --> 00:05:26,176 In other words: the only way that it's not a prime 103 00:05:26,176 --> 00:05:28,268 is that we got extremely unlucky. 104 00:05:28,268 --> 00:05:34,009 In fact, so unlucky that a negligible-probability event just happened. 105 00:05:34,009 --> 00:05:35,910 Another way to say this is that, 106 00:05:35,910 --> 00:05:39,370 if you look at the set of all 1024-bit integers, 107 00:05:39,370 --> 00:05:43,737 then, well, there is the set of primes, when we write "prime" here, 108 00:05:43,737 --> 00:05:46,360 and then there is a small number of composites 109 00:05:46,360 --> 00:05:48,334 that actually will falsify the test, 110 00:05:48,334 --> 00:05:51,072 let's call them F for "false primes". 111 00:05:51,072 --> 00:05:54,201 Let's call them FP, for "false primes". 112 00:05:54,201 --> 00:05:56,132 There is a very small number of composites 113 00:05:56,132 --> 00:05:58,995 that are not prime and yet will pass this test, 114 00:05:58,995 --> 00:06:01,853 but as we choose random integers 115 00:06:01,853 --> 00:06:04,660 - you know, we choose one here and one here, and so on - 116 00:06:04,660 --> 00:06:05,924 as we choose random integers, 117 00:06:05,924 --> 00:06:09,036 the probability that we fall into this set of false primes 118 00:06:09,036 --> 00:06:12,952 is so small that it's essentially a negligible event 119 00:06:12,952 --> 00:06:14,535 that we can ignore. 120 00:06:14,535 --> 00:06:17,043 In other words, one can prove that the set of false primes 121 00:06:17,043 --> 00:06:18,534 is extremely small, 122 00:06:18,534 --> 00:06:24,136 and a random choice is unlikely to pick such a false prime. 123 00:06:24,136 --> 00:06:24,740 Now I should mention, 124 00:06:24,740 --> 00:06:27,588 in fact, this is a very simple algorithm for generating primes. 125 00:06:27,588 --> 00:06:29,789 It's actually by far not the best algorithm. 126 00:06:29,789 --> 00:06:31,735 We have much better algorithms now. 127 00:06:31,735 --> 00:06:33,242 And in fact, once you have a candidate prime 128 00:06:33,242 --> 00:06:35,269 we now have very efficient algorithms 129 00:06:35,269 --> 00:06:37,069 that will actually prove beyond a doubt 130 00:06:37,069 --> 00:06:40,328 that this candidate prime really is a prime. 131 00:06:40,328 --> 00:06:43,003 So we don't even have to rely on probabilistic statements. 132 00:06:43,003 --> 00:06:43,578 And nevertheless, 133 00:06:43,578 --> 00:06:44,843 this Fermat test is so simple 134 00:06:44,843 --> 00:06:46,415 that I just wanted to show you 135 00:06:46,415 --> 00:06:48,405 that it's an easy way to generate primes 136 00:06:48,405 --> 00:06:52,075 although in reality this is not how primes are generated. 137 00:06:52,075 --> 00:06:54,336 As a last point, I'll say that 138 00:06:54,336 --> 00:06:56,973 you might be wondering how many times this iteration 139 00:06:56,973 --> 00:07:00,004 has to repeat until we actually find a prime. 140 00:07:00,004 --> 00:07:01,473 And that's actually a classic result, 141 00:07:01,473 --> 00:07:02,876 it's called the Prime Number Theorem 142 00:07:02,876 --> 00:07:03,884 which says that 143 00:07:03,884 --> 00:07:05,338 after a few hundred iterations 144 00:07:05,338 --> 00:07:08,675 we'll find a prime with high probability. 145 00:07:08,675 --> 00:07:10,338 So expectation, one would expect 146 00:07:10,338 --> 00:07:14,075 a few hundred iterations, no more. 147 00:07:14,075 --> 00:07:15,930 Now that we understand Fermat's theorem, 148 00:07:15,930 --> 00:07:17,607 the next thing I want to talk about is 149 00:07:17,607 --> 00:07:20,213 what's called the structure of (Z_p)*. 150 00:07:20,213 --> 00:07:22,116 So here we're going to move a hundred years into the future, 151 00:07:22,116 --> 00:07:23,735 into the 18th century, 152 00:07:23,735 --> 00:07:25,523 and look at the work of Euler. 153 00:07:25,523 --> 00:07:27,282 And one of the first things Euler showed 154 00:07:27,282 --> 00:07:29,328 is, in modern language, 155 00:07:29,328 --> 00:07:32,810 is that (Z_p)* is what's called a cyclic group. 156 00:07:32,810 --> 00:07:35,473 So what does it mean that (Z_p)* is a cyclic group? 157 00:07:35,473 --> 00:07:36,078 What it means is: 158 00:07:36,078 --> 00:07:39,771 there exists some element g in (Z_p)* 159 00:07:39,771 --> 00:07:43,368 such that if we take g and raise it to a bunch of powers, 160 00:07:43,368 --> 00:07:47,098 g, g^2, g^3, g^4 and so on and so forth 161 00:07:47,098 --> 00:07:50,672 up until we reach g^(p-2) 162 00:07:50,672 --> 00:07:53,160 - notice there is no point of going beyond g^(p-2) 163 00:07:53,160 --> 00:07:57,805 because g^(p-1) by Fermat's theorem is equal to 1, 164 00:07:57,805 --> 00:08:00,208 so then we will cycle back to 1 165 00:08:00,208 --> 00:08:02,223 if we go back to g^(p-1), 166 00:08:02,223 --> 00:08:04,651 then g^p will be equal to g, 167 00:08:04,651 --> 00:08:07,425 g^(p+1) will be equal to g^2, and so on and so forth, 168 00:08:07,425 --> 00:08:08,598 so we'll actually get a cycle 169 00:08:08,598 --> 00:08:11,529 if we keep raising to higher and higher powers of g, 170 00:08:11,529 --> 00:08:17,337 so we might as well stop at the power of g^(p-2). 171 00:08:17,337 --> 00:08:18,368 And what Euler showed is 172 00:08:18,368 --> 00:08:20,343 that in fact there is an element g 173 00:08:20,343 --> 00:08:22,728 such that if we look at all of its powers, 174 00:08:22,728 --> 00:08:26,934 all of its powers span the entire group (Z_p)*. 175 00:08:26,934 --> 00:08:30,817 Powers of g give us all the elements in (Z_p)*. 176 00:08:30,817 --> 00:08:33,335 An element of this type is called a generator. 177 00:08:33,335 --> 00:08:36,854 So g would be said to be a generator of (Z_p)*. 178 00:08:36,854 --> 00:08:38,031 So let's look at a quick example. 179 00:08:38,031 --> 00:08:40,386 Let's look for example at p=7, 180 00:08:40,386 --> 00:08:43,541 and let's look at all the powers of 3, 181 00:08:43,541 --> 00:08:47,011 which are 3^2, 3^3, 3^4, 3^5. 182 00:08:47,011 --> 00:08:51,788 3^6 already, we know, is equal to 1 modulo 7 by Fermat's theorem, 183 00:08:51,788 --> 00:08:53,869 so there's no point in looking at 3^6: 184 00:08:53,869 --> 00:08:56,176 we know we would just get 1. 185 00:08:56,176 --> 00:08:58,077 So here I calculated all of these powers for you, 186 00:08:58,077 --> 00:08:59,344 and I wrote them out, 187 00:08:59,344 --> 00:09:03,505 and you see that in fact, we get all the numbers in (Z_7)*. 188 00:09:03,505 --> 00:09:10,081 In other words, we get 1, 2, 3, 4, 5 and 6. 189 00:09:10,081 --> 00:09:14,245 So we would say that 3 is a generator of (Z_7)*. 190 00:09:14,245 --> 00:09:17,212 Now I should point out that not every element is a generator. 191 00:09:17,212 --> 00:09:20,601 For example, if we look at all the powers of 2, 192 00:09:20,601 --> 00:09:23,033 well, that's not going to generate the entire group. 193 00:09:23,033 --> 00:09:25,881 In particular, if we look at 2^0, we get 1. 194 00:09:25,881 --> 00:09:28,310 2^1, we get 2. 195 00:09:28,310 --> 00:09:33,804 2^2 is 4, and 2^3 is 8, which is 1 modulo 7. 196 00:09:33,804 --> 00:09:35,398 So we cycled back. 197 00:09:35,398 --> 00:09:37,149 And then 2^4 would be 2, 198 00:09:37,149 --> 00:09:40,196 2^5 would be 4, and so on and so forth. 199 00:09:40,196 --> 00:09:41,923 So if we look at the powers of 2, 200 00:09:41,923 --> 00:09:43,951 we just get 1, 2 and 4. 201 00:09:43,951 --> 00:09:45,133 We don't get the whole group. 202 00:09:45,133 --> 00:09:49,952 And therefore we say that 2 is not a generator of (Z_7)*. 203 00:09:49,952 --> 00:09:51,787 Now again, something that we'll use very often 204 00:09:51,787 --> 00:09:56,198 is, given an element g of (Z_p)*, 205 00:09:56,198 --> 00:09:59,786 if we look at the set of all powers of g, 206 00:09:59,786 --> 00:10:01,972 the resulting set is going to be called 207 00:10:01,972 --> 00:10:04,953 the group generated by g. 208 00:10:04,953 --> 00:10:07,309 OK? So these are all the powers of g, 209 00:10:07,309 --> 00:10:10,508 they give us what's called a multiplicative group, 210 00:10:10,508 --> 00:10:12,000 again, the technical term doesn't matter, 211 00:10:12,000 --> 00:10:14,705 the point is: we're going to call all these powers of g 212 00:10:14,705 --> 00:10:17,566 the group generated by g. 213 00:10:17,566 --> 00:10:20,111 In fact, there's this notation which I don't use very often: 214 00:10:20,111 --> 00:10:26,210 "" to denote this group that's generated by g. 215 00:10:26,210 --> 00:10:28,971 And then we call the order of g in (Z_p)*, 216 00:10:28,971 --> 00:10:30,623 we simply let that be 217 00:10:30,623 --> 00:10:33,406 the size of the group that's generated by g. 218 00:10:33,406 --> 00:10:35,982 So in other words, 219 00:10:35,982 --> 00:10:36,801 the order of g in (Z_p)* 220 00:10:36,801 --> 00:10:38,680 is the size of this group. 221 00:10:38,680 --> 00:10:40,139 But another way to think about that 222 00:10:40,139 --> 00:10:43,299 is basically, it's the smallest integer a 223 00:10:43,299 --> 00:10:48,170 such that g^a is equal to 1 in Z_p. 224 00:10:48,170 --> 00:10:50,073 OK? It's basically the smallest power 225 00:10:50,073 --> 00:10:53,758 that causes a power of g to be equal to 1. 226 00:10:53,758 --> 00:10:54,487 And it's very easy to see that 227 00:10:54,487 --> 00:10:55,838 this equality here, 228 00:10:55,838 --> 00:10:58,825 basically if we look at all the powers of g 229 00:10:58,825 --> 00:11:03,422 - we look at 1, g, g^2, g^3 and so on and so forth, 230 00:11:03,422 --> 00:11:07,023 up until we get to g to the order of g minus 1, 231 00:11:07,023 --> 00:11:10,945 and then if we look at g to the order of g, 232 00:11:10,945 --> 00:11:14,413 this thing is simply going to be equal to 1 by definition. 233 00:11:14,463 --> 00:11:16,751 OK? So there's no point in looking into higher powers, 234 00:11:16,951 --> 00:11:19,305 we might as well just stop raising to powers here. 235 00:11:19,405 --> 00:11:25,680 And as a result, the size of the set, 236 00:11:25,680 --> 00:11:29,548 in fact, is the order of g. 237 00:11:29,548 --> 00:11:32,198 And you can see that the order is the smallest power 238 00:11:32,198 --> 00:11:34,024 such that raising g to that power 239 00:11:34,024 --> 00:11:37,584 gives us 1 in Z_p. 240 00:11:37,584 --> 00:11:38,757 So I hope this is clear, 241 00:11:38,757 --> 00:11:40,399 although it might take a little lateral thinking 242 00:11:40,399 --> 00:11:41,910 to absorb all this notation. 243 00:11:41,910 --> 00:11:44,573 But in the meantime, let's look at a few examples. 244 00:11:44,573 --> 00:11:48,064 So again, let's fix our prime to be 7. 245 00:11:48,064 --> 00:11:50,289 And let's look at the order of a number of elements. 246 00:11:50,289 --> 00:11:52,883 So what is the order of 3 modulo 7? 247 00:11:52,883 --> 00:11:55,099 Well, we're asking: what is the size of the group 248 00:11:55,099 --> 00:11:58,153 that 3 generates modulo 7? 249 00:11:58,153 --> 00:12:01,195 Well, we said that 3 is a generator of (Z_7)*, 250 00:12:01,195 --> 00:12:03,887 so it generates all of (Z_7)*. 251 00:12:03,887 --> 00:12:06,478 There are 6 elements in (Z_7)*. 252 00:12:06,478 --> 00:12:11,572 And therefore we say that the order of 3 is equal to 6. 253 00:12:11,572 --> 00:12:12,309 Similarly I can ask: 254 00:12:12,309 --> 00:12:14,667 well, what is the order of 2 modulo 7? 255 00:12:14,667 --> 00:12:17,295 And in fact, we already saw the answer. 256 00:12:17,295 --> 00:12:20,669 So, let's - I'll ask you, what is the order of 2 modulo 7 257 00:12:20,669 --> 00:12:25,437 and see if you can figure out what this answer is. 258 00:12:25,437 --> 00:12:26,868 So the answer is 3. 259 00:12:26,868 --> 00:12:27,853 And again, the reason is, 260 00:12:27,853 --> 00:12:31,662 if we look at the set of powers of 2 modulo 7, 261 00:12:31,662 --> 00:12:34,376 well, we have 1, 2, 2^2, 262 00:12:34,376 --> 00:12:36,847 and then 2^3 that's already equal to 1, 263 00:12:36,847 --> 00:12:40,077 so this is the entire set of powers of 2 modulo 7. 264 00:12:40,077 --> 00:12:42,472 There are only three of them. 265 00:12:42,472 --> 00:12:46,295 And therefore, the order of 2 modulo 7 is exactly 3. 266 00:12:46,295 --> 00:12:47,327 Now let me ask you a trick question: 267 00:12:47,327 --> 00:12:51,809 What's the order of 1 modulo 7? 268 00:12:51,809 --> 00:12:52,904 Well, the answer is 1, 269 00:12:52,904 --> 00:12:55,963 because if you look at the group that's generated by 1, 270 00:12:55,963 --> 00:12:57,707 well, there's only one number in that group, 271 00:12:57,707 --> 00:12:58,842 namely the number 1. 272 00:12:58,842 --> 00:13:00,282 If I raise 1 to a whole bunch of powers, 273 00:13:00,282 --> 00:13:01,872 I'm always going to get 1, 274 00:13:01,872 --> 00:13:04,337 and therefore the order of 1 modulo 7, 275 00:13:04,337 --> 00:13:06,468 in fact, the order of 1 modulo any prime, 276 00:13:06,468 --> 00:13:10,285 is always going to be 1. 277 00:13:10,285 --> 00:13:12,276 Now, there's an important theorem of Lagrange that 278 00:13:12,276 --> 00:13:15,788 - actually, this is a very very special case of what I was telling here. 279 00:13:15,788 --> 00:13:18,206 But Lagrange's theorem basically implies 280 00:13:18,206 --> 00:13:20,877 that if you look at the order of g modulo p, 281 00:13:20,877 --> 00:13:24,173 the order is always going to divide p-1. 282 00:13:24,173 --> 00:13:26,669 So in our two example[s], you see 283 00:13:26,669 --> 00:13:30,440 6 divides 7 minus 1. 6 divides 6. 284 00:13:30,440 --> 00:13:35,206 And similarly, 3 divides 7-1, namely again, 3 divides 6. 285 00:13:35,206 --> 00:13:36,608 But this is very general. 286 00:13:36,608 --> 00:13:40,273 The order is always going to be a factor of p-1. 287 00:13:40,273 --> 00:13:40,882 In fact, I'll tell you, 288 00:13:40,882 --> 00:13:42,431 maybe it's a puzzle for you to think about 289 00:13:42,431 --> 00:13:45,249 it's actually very easy to deduce Fermat's theorem 290 00:13:45,249 --> 00:13:49,152 directly from this fact, from this Lagrange's theorem fact, 291 00:13:49,152 --> 00:13:50,859 and so Fermat's theorem really in some sense 292 00:13:50,859 --> 00:13:55,795 follows directly from Lagrange's theorem. 293 00:13:55,795 --> 00:13:58,452 Lagrange, by the way, did this work in the 19th century, 294 00:13:58,452 --> 00:14:01,819 so we can already see how we're making progress through time. 295 00:14:01,819 --> 00:14:03,422 We started in Greek times, 296 00:14:03,422 --> 00:14:07,777 and already we ended up in the 19th century. 297 00:14:07,777 --> 00:14:09,246 And I can tell you that more advanced crypto 298 00:14:09,246 --> 00:14:13,302 actually uses 20th-century math very extensively. 299 00:14:13,302 --> 00:14:15,635 Now that we understand the structure of (Z_p)*, 300 00:14:15,635 --> 00:14:17,435 let's generalize that to composites 301 00:14:17,435 --> 00:14:19,963 and look at the structure of (Z_N)*. 302 00:14:19,963 --> 00:14:22,755 So what I want to show you here is what's called Euler's theorem, 303 00:14:22,755 --> 00:14:26,220 which is a direct generalization of Fermat's theorem. 304 00:14:26,220 --> 00:14:28,552 So Euler defined the following function: 305 00:14:28,552 --> 00:14:30,403 So given an integer N, 306 00:14:30,403 --> 00:14:33,573 we define what's called the phi function, phi of N, 307 00:14:33,573 --> 00:14:37,622 to be basically the size of the set (Z_N)*. 308 00:14:37,622 --> 00:14:40,225 This is sometimes called "Euler's phi function". 309 00:14:40,225 --> 00:14:42,786 The size of the set (Z_N)*. 310 00:14:42,786 --> 00:14:46,063 So for example, we already looked at (Z_12)*. 311 00:14:46,063 --> 00:14:49,171 We said that (Z_12)* contains these four elements 312 00:14:49,171 --> 00:14:51,206 1, 5, 7 and 11, 313 00:14:51,206 --> 00:14:56,014 and therefore we say that phi of 12 is simply the number of 4. 314 00:14:56,014 --> 00:14:57,214 So let me ask you as a puzzle: 315 00:14:57,214 --> 00:14:59,294 What is phi of p? 316 00:14:59,294 --> 00:15:04,071 It'll basically be the size of (Z_P)*. 317 00:15:04,071 --> 00:15:05,152 And so in fact we said 318 00:15:05,152 --> 00:15:08,139 that (Z_P)* contains all of Z_P 319 00:15:08,139 --> 00:15:09,933 except for the number zero, 320 00:15:09,933 --> 00:15:12,983 and therefore phi of p for any prime p 321 00:15:12,983 --> 00:15:16,740 is going to be p-1. 322 00:15:16,740 --> 00:15:18,700 Now there's a special case which I'm going to state here 323 00:15:18,700 --> 00:15:21,013 we're going to use later for the RSA system: 324 00:15:21,013 --> 00:15:23,567 if N happens to be a product of two primes, 325 00:15:23,567 --> 00:15:27,505 then phi of N is simply N minus p minus q plus 1. 326 00:15:27,505 --> 00:15:29,554 Let me just show you why that's true. 327 00:15:29,554 --> 00:15:32,435 Basically, N is the size of Z_N. 328 00:15:32,435 --> 00:15:34,562 And now we need to remove all the elements 329 00:15:34,562 --> 00:15:37,209 that are not relatively prime to N. 330 00:15:37,209 --> 00:15:40,015 Well, how can an element not be relatively prime to N? 331 00:15:40,015 --> 00:15:41,495 It's got to be divisible by p, 332 00:15:41,495 --> 00:15:43,747 or it's got to be divisible by q. 333 00:15:43,747 --> 00:15:45,757 Well, how many elements between zero and N-1 334 00:15:45,757 --> 00:15:48,881 are there that are divisible by p? 335 00:15:48,881 --> 00:15:50,429 Well, there are exactly q of them. 336 00:15:50,429 --> 00:15:53,005 How many elements are there that are divisible by q? 337 00:15:53,005 --> 00:15:54,509 Well, there are exactly p of them. 338 00:15:54,509 --> 00:15:57,971 So we subtract p to get rid of those divisible by q, 339 00:15:57,971 --> 00:16:01,104 we subtract q to get rid of those divisible by p. 340 00:16:01,104 --> 00:16:03,793 And you'll notice we subtracted 0 twice, 341 00:16:03,793 --> 00:16:07,671 because 0 is divisible both by p and q. 342 00:16:07,671 --> 00:16:09,246 And therefore we add 1, 343 00:16:09,246 --> 00:16:12,190 just to make sure we subtract 0 only once. 344 00:16:12,190 --> 00:16:13,178 And so it's not difficult to see 345 00:16:13,178 --> 00:16:17,057 that phi of N is N minus p minus q plus 1. 346 00:16:17,057 --> 00:16:18,371 And another way of writing that is simply: 347 00:16:18,371 --> 00:16:22,438 p minus 1, times q minus 1. 348 00:16:22,438 --> 00:16:24,212 OK? So this is a fact that we will use 349 00:16:24,212 --> 00:16:25,909 later on when we will come back 350 00:16:25,909 --> 00:16:29,420 and talk about the RSA system. 351 00:16:29,420 --> 00:16:32,689 So far, this is just defining this phi function of Euler. 352 00:16:32,689 --> 00:16:35,830 But now, Euler put this phi function to really good use. 353 00:16:35,830 --> 00:16:38,003 And what he proved is this amazing fact here 354 00:16:38,003 --> 00:16:39,177 that basically says 355 00:16:39,177 --> 00:16:43,069 that if you give me any element x in (Z_N)*, 356 00:16:43,069 --> 00:16:44,576 in fact it so happens that 357 00:16:44,576 --> 00:16:48,772 x to the power of phi of N is equal to 1 in Z_N. 358 00:16:48,772 --> 00:16:50,984 So you can see that this is a generalization of Fermat's theorem. 359 00:16:50,984 --> 00:16:53,994 In particular, Fermat's theorem only applied to primes. 360 00:16:53,994 --> 00:16:57,337 For primes we know that phi of p is equal to p-1, 361 00:16:57,337 --> 00:16:57,975 and in other words, 362 00:16:57,975 --> 00:17:01,336 if N were prime, we would simply write p-1 here, 363 00:17:01,336 --> 00:17:04,457 and then we would get exactly Fermat's theorem. 364 00:17:04,457 --> 00:17:06,124 The beauty of Euler's theorem is that 365 00:17:06,124 --> 00:17:09,252 it applies to composites and not just primes. 366 00:17:09,706 --> 00:17:13,758 So let's look at some examples: 367 00:17:13,758 --> 00:17:17,415 So let's look at 5 to the power of phi of 12. 368 00:17:17,415 --> 00:17:20,438 So 5 is an element of (Z_12)*. 369 00:17:20,438 --> 00:17:22,712 If we raise it to the power of phi of 12, 370 00:17:22,712 --> 00:17:24,105 we should be getting 1. 371 00:17:24,105 --> 00:17:26,477 Well, we know that phi of 12 is 4, 372 00:17:26,477 --> 00:17:29,801 so we're raising 5 to the power of 4. 373 00:17:29,801 --> 00:17:31,998 5 to the power of 4 is 625. 374 00:17:31,998 --> 00:17:33,471 And it's a simple calculation to show that 375 00:17:33,471 --> 00:17:36,428 that's equal to 1 modulo 12. 376 00:17:36,428 --> 00:17:37,789 So this is proof by example, 377 00:17:37,789 --> 00:17:38,955 but of course it's not a proof at all, 378 00:17:38,955 --> 00:17:40,124 it's just an example. 379 00:17:40,124 --> 00:17:42,485 And in fact, it's not difficult to prove Euler's theorem. 380 00:17:42,485 --> 00:17:44,375 And in fact I tell you that Euler's theorem 381 00:17:44,375 --> 00:17:46,120 is also a very special case 382 00:17:46,120 --> 00:17:49,366 of Lagrange's general theorem. 383 00:17:49,366 --> 00:17:51,437 OK. So we said that 384 00:17:51,437 --> 00:17:53,576 this is a generalization of Fermat's theorem 385 00:17:53,576 --> 00:17:54,959 and in fact, as we'll see, 386 00:17:54,959 --> 00:17:56,004 this Euler's theorem 387 00:17:56,004 --> 00:18:00,205 is the basis of the RSA cryptosystem. 388 00:18:00,205 --> 00:18:00,950 So I'll stop here, 389 00:18:00,950 --> 00:18:03,278 and we'll continue with modular quadratic equations 390 00:18:03,278 --> 99:59:59,999 in the next segment.