1 00:00:00,000 --> 00:00:04,220 In the previous segment we talked about modular inversion and we said the Euclid's 2 00:00:04,220 --> 00:00:08,238 algorithm gives us an efficient way to find the inverse of an element modulo N. 3 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 4 00:00:12,256 --> 00:00:15,866 the seventeenth and eighteenth century where we're going to talk about 5 00:00:15,866 --> 00:00:19,986 Fermat and Euler contributions. Before that let's do a quick review of 6 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 7 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 8 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 9 00:00:32,445 --> 00:00:36,761 denote a prime. Now we said that ZN is a set of integers from zero 10 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 11 00:00:41,370 --> 00:00:46,186 also said that ZN star is basically the set of invertible elements in ZN. And we 12 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 13 00:00:51,243 --> 00:00:55,879 prime to N. And not only did we completely understand which elements are 14 00:00:55,879 --> 00:01:00,635 invertible and which aren't, we also showed a very efficient algorithm based on 15 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 16 00:01:05,572 --> 00:01:10,388 that the running time of this algorithm, is basically order n squared, where 17 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 18 00:01:16,107 --> 00:01:21,037 we're going to move from Greek times all the way to the seventeenth century and 19 00:01:21,037 --> 00:01:26,276 talk about Fermat. So Fermat did a number of important theorems. The one that I want 20 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 21 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 22 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 23 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 24 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, 25 00:01:50,645 --> 00:01:55,286 which in fact, is one modulo five. This example satisfies Fermat's theorem. 26 00:01:55,286 --> 00:01:59,521 Interestingly, Fermat actually didn't prove this theorem himself. The proof 27 00:01:59,521 --> 00:02:04,337 actually waited until Euler, who proved that almost 100 years later. And in 28 00:02:04,337 --> 00:02:09,122 fact, he proved a much more general version of this theorem. So let's look at 29 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 30 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 31 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 32 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 33 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 34 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. 35 00:02:39,310 --> 00:02:44,042 So this gives us another algorithm for finding the inverse of X modulo a prime. 36 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 37 00:02:48,835 --> 00:02:53,508 x. It turns out, actually this is a fine way to compute inverses modulo a prime. 38 00:02:53,508 --> 00:02:58,301 But it has two deficiencies compared to Euclid's algorithm. First of all, it only 39 00:02:58,301 --> 00:03:02,528 works modulo primes, Whereas, Euclid's algorithm worked modulo composites as 40 00:03:02,528 --> 00:03:07,017 well. And second of all, it turns out this algorithm is actually less efficient. When 41 00:03:07,017 --> 00:03:10,911 we talk about how to do modular exponentiations--we're gonna do that in 42 00:03:10,911 --> 00:03:15,345 the last segment in this module--you'll see that the running time to compute this 43 00:03:15,345 --> 00:03:19,792 exponentiation is actually cubic in the size of P. So this will take roughly log 44 00:03:19,792 --> 00:03:24,266 cube of P, whereas if you remember, Euclid's algorithm was able to compute the 45 00:03:24,266 --> 00:03:30,343 inverse in quadratic time in the representation of P. So not only is this 46 00:03:30,343 --> 00:03:36,512 algorithm less general it only works for primes, it's also less efficient. So score 47 00:03:36,512 --> 00:03:41,473 one for Euclid. But nevertheless, this fact about primes is extremely important, 48 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 49 00:03:47,506 --> 00:03:52,155 show you a quick and simple application for Fermat's theorem suppose we wanted 50 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 51 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 52 00:04:02,006 --> 00:04:06,724 a very simple probabilistic algorithm. What we would do is we would choose a 53 00:04:06,724 --> 00:04:11,938 random integer in the interval that was specified. And then we would test whether 54 00:04:12,124 --> 00:04:17,153 this integer satisfies Fermat's theorem. In other words, we would test for example 55 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 56 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 57 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 58 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 59 00:04:37,284 --> 00:04:41,782 again and again, until finally we find an integer that satisfies this condition. And 60 00:04:41,782 --> 00:04:46,009 once we find an integer that satisfies this condition, we simply output it and 61 00:04:46,009 --> 00:04:51,573 stop. Now it turns out, this is actually a fairly difficult statement to prove. But 62 00:04:51,573 --> 00:04:56,305 it turns out if a random number passes this test, then it's extremely likely to 63 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 64 00:05:01,398 --> 00:05:06,191 like less than two to the -60 for the range of 1024 bit numbers. As the 65 00:05:06,191 --> 00:05:10,744 number gets bigger and bigger the probability that it passes this test here, 66 00:05:10,744 --> 00:05:15,716 but is not a prime drops to zero very quickly. So this is actually quite an 67 00:05:15,716 --> 00:05:20,455 interesting algorithm. You realize we're not guaranteed that the output is in fact 68 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 69 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 70 00:05:29,587 --> 00:05:34,298 unlucky that a negligible probability event just happened. Another way to say 71 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 72 00:05:40,230 --> 00:05:45,233 of primes. Let me write prime here. And then there is a small number of 73 00:05:45,233 --> 00:05:50,805 composites. That actually will falsify the test. Let's call them F for false primes. 74 00:05:50,805 --> 00:05:55,653 Let's call them FP, for false primes. There's a very small number of composites 75 00:05:55,653 --> 00:06:00,626 that are not prime and yet will pass this test. But as we choose random integers, 76 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 77 00:06:05,349 --> 00:06:10,260 integers, the probability that we fall into the set of false primes is so small 78 00:06:10,260 --> 00:06:15,082 That it's essentially a negligible event that we can ignore. In other words, one 79 00:06:15,082 --> 00:06:20,591 can prove that the set of false primes is extremely small, and a random choice is 80 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 81 00:06:25,266 --> 00:06:28,960 simple algorithm for generating primes. It's actually, by far, not the best 82 00:06:28,960 --> 00:06:32,654 algorithm. We have much better algorithms now. And, in fact, once you have a 83 00:06:32,654 --> 00:06:36,349 candidate prime, we now have very efficient algorithms that will actually 84 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 85 00:06:40,498 --> 00:06:44,597 have to rely on probabilistic statements. But nevertheless, this Fermat test is so 86 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. 87 00:06:48,595 --> 00:06:53,076 Although in reality, this is not how primes are generated. As the last point, 88 00:06:53,076 --> 00:06:57,468 I'll say that you might be wondering how many times this iteration has to repeat 89 00:06:57,468 --> 00:07:01,536 until we actually find the prime. And that's actually a classic result; it's 90 00:07:01,536 --> 00:07:05,820 called the prime number theorem, which says that, after a few hundred iterations, 91 00:07:05,820 --> 00:07:09,833 in fact, we'll find the prime with high probability. So in expectation, one would 92 00:07:09,833 --> 00:07:14,771 expect a few hundred iterations and no more. Now that we understand 93 00:07:14,771 --> 00:07:19,314 Fermat's theorem, the next thing I want to talk about is what's called the 94 00:07:19,314 --> 00:07:23,915 structure of ZP star. So here, we are going to move 100 years into the future... 95 00:07:23,915 --> 00:07:28,576 Into the eighteenth century and look at the work of Euler. And one of the first 96 00:07:28,576 --> 00:07:33,118 things Euler showed is in modern language is that ZP star is what's called a 97 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 98 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 99 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 100 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 101 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 102 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 103 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 104 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 105 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. 106 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 107 00:08:21,413 --> 00:08:26,300 look at all of its powers all of its powers expand the entire group ZP Star. 108 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 109 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 110 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 111 00:08:40,696 --> 00:08:45,575 look at all the powers of three. So three squared three cubed, three to the fourth, 112 00:08:45,575 --> 00:08:50,130 three to the fifth, Three to the six, already we know, is equal to one modular 113 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 114 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 115 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, 116 00:09:04,431 --> 00:09:09,313 in Z7 star. In other words, we get one, two, three, four, five, and six. So 117 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 118 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, 119 00:09:19,886 --> 00:09:24,914 that's not gonna generate the entire group. In particular, if we look at two to 120 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 121 00:09:29,650 --> 00:09:34,455 cubed is eight, which is one modular seven. So we cycled back and then two to 122 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 123 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 124 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, 125 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 126 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 127 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 128 00:10:06,947 --> 00:10:12,798 multiplicative group. Again, the technical term doesn't matter. The point is we're 129 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 130 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 131 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 132 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 133 00:10:35,663 --> 00:10:40,626 p star is the size of this group. But another way to think about that is 134 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. 135 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 136 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 137 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 138 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 139 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. 140 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 141 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 142 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 143 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 144 00:11:38,931 --> 00:11:43,455 might take a little bit of thinking to absorb all this notation. But in the 145 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 146 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 147 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 148 00:11:57,752 --> 00:12:02,759 three generates modulus of seven? Well, we said that three is a generator of Z7 star. 149 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 150 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 151 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, 152 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 153 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 154 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 155 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 156 00:12:39,077 --> 00:12:44,211 seven. There are only three of them and, therefore, the order of two modulo seven 157 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 158 00:12:49,215 --> 00:12:54,499 modulo seven? Well, the answer is one. Because if you look at the group that's 159 00:12:54,499 --> 00:12:58,633 generated by one, well, there's only one number in that group, namely the number 160 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 161 00:13:02,608 --> 00:13:07,060 therefore the order of 1 modulo 7 In fact the order of 1 modulo any prime 162 00:13:07,060 --> 00:13:12,518 is always gonna be 1. Now there's an important theorem of Lagrange, that 163 00:13:12,518 --> 00:13:17,137 actually this is a very, very special case of it, what I am stating here. But 164 00:13:17,137 --> 00:13:22,309 Langrage's theorem basically implies that if you look at the order of G modulo p, 165 00:13:22,309 --> 00:13:27,112 the order is always going to divide P-1. So in our two example you see, 166 00:13:27,297 --> 00:13:32,100 six divides seven minus one, six divides six, and similarly, three divides seven 167 00:13:32,100 --> 00:13:37,026 minus one. Namely again three divides six. But this is very general; your order is 168 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 169 00:13:41,333 --> 00:13:45,177 puzzle for you to think about. It's actually very easy to deduce Fermat's 170 00:13:45,177 --> 00:13:49,179 theorem directly from this fact, from this Lagrange's theorem in fact. And so 171 00:13:49,179 --> 00:13:53,340 Fermat's theorem really in some sense follows directly from Lagrange's theorem. 172 00:13:54,580 --> 00:13:59,375 Lagrange, by the way, did his work in the nineteenth century, so you can already see 173 00:13:59,375 --> 00:14:04,053 how we're making progress through time. We started in Greek times, and already we 174 00:14:04,053 --> 00:14:09,376 ended up in the nineteenth century. And I can tell you that more advanced crypto 175 00:14:09,376 --> 00:14:14,024 actually uses twentieth century math very extensively. Now that we understand the 176 00:14:14,024 --> 00:14:18,416 structure of ZP star, let's generalize that to composites, and look at the 177 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 178 00:14:23,471 --> 00:14:28,044 which is a, a direct generalization of Fermat's Theorem. So, Euler defined the 179 00:14:28,044 --> 00:14:32,978 following function. So given an integer N, he defined what's called the phi 180 00:14:32,978 --> 00:14:37,190 function, phi of M, to be basically the size of the set ZN star. 181 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 182 00:14:42,686 --> 00:14:48,521 for example, we already looked at Z twelve star. We said that Z twelve star contains 183 00:14:48,521 --> 00:14:53,881 these four elements, one, five, seven, and eleven. And therefore we say that phi of 184 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? 185 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 186 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 187 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 188 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 189 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 190 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 191 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 192 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 193 00:15:42,632 --> 00:15:47,079 divisible by q. Well how many elements between zero and m minus one are there, 194 00:15:47,079 --> 00:15:51,757 there that are divisible by p? Well there are exactly q of them. How many elements 195 00:15:51,757 --> 00:15:55,973 are there that are divisible by q. Well there are exactly p of them. So we 196 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 197 00:16:00,593 --> 00:16:05,776 divisible by p. And you notice we subtracted zero twice, because zero is 198 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 199 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 200 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 201 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 202 00:16:30,275 --> 00:16:35,690 this phi function of Euler. But now Euler put this phi function to really good use. 203 00:16:35,690 --> 00:16:41,104 And what he proved is this amazing fact here that basically says that if you give 204 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) 205 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 206 00:16:50,678 --> 00:16:55,239 theorem; in particular, Fermat's theorem only applied to primes. For primes we know 207 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 208 00:16:59,913 --> 00:17:04,494 simply write p minus one here, and then we would get exactly Fermat's theorem. The 209 00:17:04,494 --> 00:17:08,892 beauty of Euler's theorem is that it applies to composites, and not just 210 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). 211 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 212 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 213 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 214 00:17:32,037 --> 00:17:36,227 calculation to show that that's equal to 1 modulo 12. So this is proof 215 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 216 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 217 00:17:44,555 --> 00:17:48,900 Euler's theorem is also a very special case of Lagrange's general theorem. 218 00:17:49,880 --> 00:17:53,888 Okay so we say that this is a generalization of Fermat's theorem and 219 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 220 00:17:58,230 --> 00:18:03,922 system. So I stop here and we continue with modular quadratic equations in the 221 00:18:03,922 --> 00:18:04,740 next segment.