0:00

In the previous segment we talked about modular inversion and we said the Euclid's

Â algorithm gives us an efficient way to find the inverse of an element modulo N.

Â In this segment we're going to forward through time and we're going to move to

Â the seventeenth and eighteenth century where we're going to talk about

Â Fermat and Euler contributions. Before that let's do a quick review of

Â what we discussed in the previous segment. So as usual I'm going to let N denote the

Â positive integer and let's just say that N happens to be a n-bit integer, in other

Â words it's between two to the n and two to the n+1, as usual we're going to let P

Â denote a prime. Now we said that ZN is a set of integers from zero

Â to N-1 and we said that we can add and multiply elements in the set modulo N. We

Â also said that ZN star is basically the set of invertible elements in ZN. And we

Â proved a simple lemma to say that, X is invertible if and only if X is relatively

Â prime to N. And not only did we completely understand which elements are

Â invertible and which aren't, we also showed a very efficient algorithm based on

Â Euclid's extended algorithm, to find the inverse of an element X in ZN. And we said

Â that the running time of this algorithm, is basically order n squared, where

Â again, n is the number of bits of the number capital N. So as I said, now

Â we're going to move from Greek times all the way to the seventeenth century and

Â talk about Fermat. So Fermat did a number of important theorems. The one that I want

Â to show you here today is the following. So suppose I give you a prime P. Then in

Â fact for any element X in ZP star, it so happens that if I look at X and raise it

Â to the power of P - 1, I'm a gonna get one, in ZP. So let's look at a quick

Â example. Suppose I set the number P to be five. And I look at, three to the power of

Â P-1. In other words, three to the power of four, Three to the power of four is 81,

Â which in fact, is one modulo five. This example satisfies Fermat's theorem.

Â Interestingly, Fermat actually didn't prove this theorem himself. The proof

Â actually waited until Euler, who proved that almost 100 years later. And in

Â fact, he proved a much more general version of this theorem. So let's look at

Â a simple application of Fermat's theorem. Suppose I look at an element X in Z P

Â star. And I want to remind you here that P [inaudible] must be a prime. Well, then what do we

Â know? We know that X to the P minus one is equal to one. Well, we can write X to the

Â P minus one as X times X to the power of P minus two. Well so now we know that X

Â times X to the power of P minus two happens to be equal to one. And what that

Â says, is that really the inverse of X modulo P, is simply X to the P minus two.

Â So this gives us another algorithm for finding the inverse of X modulo a prime.

Â Simply raise X to the power of p minus two, and that will give us the inverse of

Â x. It turns out, actually this is a fine way to compute inverses modulo a prime.

Â But it has two deficiencies compared to Euclid's algorithm. First of all, it only

Â works modulo primes, Whereas, Euclid's algorithm worked modulo composites as

Â well. And second of all, it turns out this algorithm is actually less efficient. When

Â we talk about how to do modular exponentiations--we're gonna do that in

Â the last segment in this module--you'll see that the running time to compute this

Â exponentiation is actually cubic in the size of P. So this will take roughly log

Â cube of P, whereas if you remember, Euclid's algorithm was able to compute the

Â inverse in quadratic time in the representation of P. So not only is this

Â algorithm less general it only works for primes, it's also less efficient. So score

Â one for Euclid. But nevertheless, this fact about primes is extremely important,

Â and we're gonna be making extensive use of it in the next couple of weeks. So let me

Â show you a quick and simple application for Fermat's theorem suppose we wanted

Â to generate a large random prime, say our prime needed to be 1,000 bits or so. So

Â the prime we're looking for is on the order of two to the 1024 [inaudible]. So here's

Â a very simple probabilistic algorithm. What we would do is we would choose a

Â random integer in the interval that was specified. And then we would test whether

Â this integer satisfies Fermat's theorem. In other words, we would test for example

Â using the base two; we would test whether two to the power of p minus one equals one

Â in Z p. If the answer is no, then if this equality doesn't hold, then we know for

Â sure that the number p that we chose is not a prime. And if that happens, all we

Â do is we go back to step one and we try another prime. And we do this again and

Â again and again, until finally we find an integer that satisfies this condition. And

Â once we find an integer that satisfies this condition, we simply output it and

Â stop. Now it turns out, this is actually a fairly difficult statement to prove. But

Â it turns out if a random number passes this test, then it's extremely likely to

Â be a prime. In particular the probability that P is not a prime is very small. It's

Â like less than two to the -60 for the range of 1024 bit numbers. As the

Â number gets bigger and bigger the probability that it passes this test here,

Â but is not a prime drops to zero very quickly. So this is actually quite an

Â interesting algorithm. You realize we're not guaranteed that the output is in fact

Â a prime. All we know is that it's very, very likely to be a prime. In other words

Â the only way that it's not a prime is that we got extremely unlucky. In fact so

Â unlucky that a negligible probability event just happened. Another way to say

Â this is that if you look at the set of all 1024 integers, then, well, there's the set

Â of primes. Let me write prime here. And then there is a small number of

Â composites. That actually will falsify the test. Let's call them F for false primes.

Â Let's call them FP, for false primes. There's a very small number of composites

Â that are not prime and yet will pass this test. But as we choose random integers,

Â you know, we choose one here, one here, one here, and so on, as we choose random

Â integers, the probability that we fall into the set of false primes is so small

Â That it's essentially a negligible event that we can ignore. In other words, one

Â can prove that the set of false primes is extremely small, and a random choice is

Â unlikely to pick such a false prime. Now I should mention, in fact, this is a very

Â simple algorithm for generating primes. It's actually, by far, not the best

Â algorithm. We have much better algorithms now. And, in fact, once you have a

Â candidate prime, we now have very efficient algorithms that will actually

Â prove beyond a doubt that this candidate prime really is a prime. So we don't even

Â have to rely on probabilistic statements. But nevertheless, this Fermat test is so

Â simple, that I just wanted to show you that it's an easy way to generate primes.

Â Although in reality, this is not how primes are generated. As the last point,

Â I'll say that you might be wondering how many times this iteration has to repeat

Â until we actually find the prime. And that's actually a classic result; it's

Â called the prime number theorem, which says that, after a few hundred iterations,

Â in fact, we'll find the prime with high probability. So in expectation, one would

Â expect a few hundred iterations and no more. Now that we understand

Â Fermat's theorem, the next thing I want to talk about is what's called the

Â structure of ZP star. So here, we are going to move 100 years into the future...

Â Into the eighteenth century and look at the work of Euler. And one of the first

Â things Euler showed is in modern language is that ZP star is what's called a

Â cyclic group. What does it mean that ZP star is a cyclic group? What it means is

Â that there exists some element G in ZP star, such that if we take G and raise to

Â a bunch of powers G, G squared, G cubed, G to the fourth. And so on and so forth up

Â until we reach G to the P minus two. Notice there's no point of going beyond G

Â to the p minus two, because G to the p minus one by Fermat's theorem is equal to

Â one, so then we will cycle back to one. If we go back to G to the p minus one, then G

Â to the p will be equal to G, G to the p plus one will be equal to G squared, and

Â so on and so forth. So we'll actually get a cycle if we keep raising to higher and

Â higher powers of G. So we might as well stop at the power of G to the p minus two.

Â And what Euler showed is that in fact there is an element G such that if you

Â look at all of its powers all of its powers expand the entire group ZP Star.

Â The powers of G give us all the elements in ZP star. Elements of this, of this type

Â is called a generator. So G would be said to be a generator of ZP star. So let's

Â look at a quick example. So let's look, for example, at P equals seven. And let's

Â look at all the powers of three. So three squared three cubed, three to the fourth,

Â three to the fifth, Three to the six, already we know, is equal to one modular

Â seven by Fermat's Theorem. So there's no point in looking at three to the six. We

Â know we would just get one. So here, I calculated all these powers for you, and I

Â wrote them out. And you see that in fact, we get all the numbers [inaudible] in Z,

Â in Z7 star. In other words, we get one, two, three, four, five, and six. So

Â we would say that three is a generator of Z7 star. Now I should point out that not

Â every element is a generator. For example, if we look at all the powers of two, well,

Â that's not gonna generate the entire group. In particular, if we look at two to

Â the zero, we get one. Two to the one, we get two. Two squared is four, and two

Â cubed is eight, which is one modular seven. So we cycled back and then two to

Â the fourth would be two, two to the fifth would be four. And so on and so forth. So

Â if we look at the powers of two, we just get one, two, and four. We don't get the

Â whole group and therefore we say that two is not a generator of Z7 star. Now again,

Â something that we'll use very often is given an element G of ZP<i>, if we look at a</i>

Â set of all powers of G, the resulting set is gonna be called the group generated by

Â G, okay? So these are all the powers of G. They give us what's called a

Â multiplicative group. Again, the technical term doesn't matter. The point is we're

Â gonna call all these powers of G, the group generated by G. In fact there's this

Â notation which I don't use very often, angle G angle, to denote this group that's

Â generated by G. And then we call the order of G in Z p star, we simply let that be

Â the size of the group that's generated by G. So in other words, the order of G in Z

Â p star is the size of this group. But another way to think about that is

Â basically it's the smallest integer A such that G to the A is equal to one in Z P.

Â 11:16

Okay, so there's no point in looking at any higher powers. We might as well just

Â stop raising to powers here. And as a result the size of the set, in fact, is

Â the order of G. And you can see that the order is the smallest power such that

Â raising G to that power gives us one in Z p. So I hope this is clear although it

Â might take a little bit of thinking to absorb all this notation. But in the

Â meantime let's look at a few examples. So, again, let's fix our, our prime to be

Â seven. And let's look at the order of the number of elements. So what is the order

Â of three modulus of seven? Well, we're asking what is the size of the group that

Â three generates modulus of seven? Well, we said that three is a generator of Z7 star.

Â So it generates all of Z7 star. There are six elements in Z7 star. And therefore we

Â say that the order of three is equal to six. Similarly, I can ask, well, what is

Â the order of two modulo seven? And in fact, we already saw the answer. So let's,

Â I'll ask you, what is the order of two modulo seven and see if you can f igure

Â out what this answer is. So the answer is three and again, the reason is if we look

Â at the set of powers of two modulo seven, we have one, two, two squared, and then

Â two cubed is already equal to one. So this is the entire set of powers of two modulo

Â seven. There are only three of them and, therefore, the order of two modulo seven

Â is exactly three. Now let me ask you a trick question. What's the order of one

Â modulo seven? Well, the answer is one. Because if you look at the group that's

Â generated by one, well, there's only one number in that group, namely the number

Â one. If I raise one to a whole bunch of powers, I'm always gonna get one, And

Â therefore the order of 1 modulo 7 In fact the order of 1 modulo any prime

Â is always gonna be 1. Now there's an important theorem of Lagrange, that

Â actually this is a very, very special case of it, what I am stating here. But

Â Langrage's theorem basically implies that if you look at the order of G modulo p,

Â the order is always going to divide P-1. So in our two example you see,

Â six divides seven minus one, six divides six, and similarly, three divides seven

Â minus one. Namely again three divides six. But this is very general; your order is

Â always going be a factor of P minus one. In fact, I'll tell you, maybe it's a

Â puzzle for you to think about. It's actually very easy to deduce Fermat's

Â theorem directly from this fact, from this Lagrange's theorem in fact. And so

Â Fermat's theorem really in some sense follows directly from Lagrange's theorem.

Â 13:54

Lagrange, by the way, did his work in the nineteenth century, so you can already see

Â how we're making progress through time. We started in Greek times, and already we

Â ended up in the nineteenth century. And I can tell you that more advanced crypto

Â actually uses twentieth century math very extensively. Now that we understand the

Â structure of ZP star, let's generalize that to composites, and look at the

Â structure of ZN star. So what I wanna show you here is what's called Euler's Theorem

Â which is a, a direct generalization of Fermat's Theorem. So, Euler defined the

Â following function. So given an integer N, he defined what's called the phi

Â function, phi of M, to be basically the size of the set ZN star.

Â This is sometimes called, Euler's phi function. The size of the set Z N star. So

Â for example, we already looked at Z twelve star. We said that Z twelve star contains

Â these four elements, one, five, seven, and eleven. And therefore we say that phi of

Â twelve is simply the number four. So let me ask you as a puzzle, what is phi of P?

Â It will basically be the size of Z P star. And so, in fact, we said that in the Z P

Â star contains all of Z P except for the number zero. And therefore, phi of P for

Â any prime P is gonna be P minus one. Now, there is a special case, which I'm gonna

Â state here and we're gonna use later for the RSA system. If N happens to be a

Â product of two primes, then phi of N is simply N minus P minus Q plus one. And let

Â me just show you why that's true. So basically N is the size of Z N. And now we

Â need to remove all the elements that are not relatively prime to m. Well how can an

Â element not be relatively prime to m? It's gotta be divisible by p or it's gotta be

Â divisible by q. Well how many elements between zero and m minus one are there,

Â there that are divisible by p? Well there are exactly q of them. How many elements

Â are there that are divisible by q. Well there are exactly p of them. So we

Â subtract p to get rid of those divisible by q. We subtract q to get rid of those

Â divisible by p. And you notice we subtracted zero twice, because zero is

Â divisible both by P and Q. And therefore, we add one just to make sure we subtract

Â zero only once. And so it's not difficult to see that phi(N) is N-P-Q+1. And another way

Â of writing that is simply (P-1) times (Q-1). Okay, so this is a fact that we will use later

Â on, when we come back and talk about the RSA system. So far, this is just defining

Â this phi function of Euler. But now Euler put this phi function to really good use.

Â And what he proved is this amazing fact here that basically says that if you give

Â me any element X in Z N star. In fact, and it so happens that X to the power of phi(N)

Â is equal to one in Z N. So you can see that this is a generalization of Fermat's

Â theorem; in particular, Fermat's theorem only applied to primes. For primes we know

Â that phi(p) is equal to p minus one, and in other words if N were prime we would

Â simply write p minus one here, and then we would get exactly Fermat's theorem. The

Â beauty of Euler's theorem is that it applies to composites, and not just

Â primes. So let's look at some examples. So let's look at five to the power of phi(12).

Â So five is an element of Z12 star. If we raise it to the power of five of

Â twelve, we should be getting one. Well, we know that phi(12) is 4, so we're

Â raising 5 to the power of 4. Five to the power of four is 625 and it's a simple

Â calculation to show that that's equal to 1 modulo 12. So this is proof

Â by example but of course it's not a proof at all. It's just an example. But in fact

Â it's not difficult to prove Euler's theorem and in fact I'll tell you that

Â Euler's theorem is also a very special case of Lagrange's general theorem.

Â