0:00

In the last module we saw that number theory can be useful for key exchange.

Â In this modlule we will review some basic facts of number theory that will help us build

Â many public key systems next week. As we go through the material in this module it

Â might help to pause the video from time to time to make sure all the examples are clear

Â So as I said we're gonna use number theory to build key exchange protocols.

Â We're gonna use number theory to build digital signatures, public encryption and many, many other things.

Â But before we can do all that, we have to review some basic

Â facts from number theory and in fact in this module we're gonna do a quick course

Â on the relevant concept. If you'd like to review some of the material discussed in

Â this module offline, I referenced at the end of the module a free textbook by

Â Victor Shoup and I pointed to some specific chapters in his book that will

Â explain the materials that we will cover here. So from here on I'm going to use the

Â following notation. I'm going to use capital N to always denote a positive

Â integer, and I'm going to use lower case p to always denote a positive prime number.

Â Now I'd like to introduce the following notation, there's this funny Z that's

Â written like two diagonal lines here with a subscript N I'm gonna use that to denote

Â the sets as zero, one, two, up to N minus one. This is actually a very common

Â notation that's used in Crypto, and so I'll stick to that here. So again, Z sub N

Â denotes the set of integers 0,1 up to N-1. And in fact, this is not just a

Â set of integers. We can do addition and multiplication in this set as long as we

Â always multiply module of the number N. For those of you who know a little bit of

Â algebra, I'll just say that Z sub N denotes a ring where addition and

Â multiplication are done modulo N. This is very common notation in crypto, although

Â in modern mathematics Z sub N sometimes denotes something else. But as I said I'm

Â gonna keep on using Z sub N to denote the set of integers 0 to N-1 with

Â addition and multiplication modulo N. So I want to make sure everybody's

Â comfortable with modular arithmetic. And so let's just look at the number, say, N=12

Â And let's just see some basic facts about modular arithmetic. So

Â I'm gonna say that nine plus eight is seventeen; seventeen is five modulo

Â twelve, so I'm gonna write that nine plus eight is equal to five in Z 12. Now

Â can someone tell me how much is five times seven in Z12? In other words, how much is modular 12?

Â 2:29

Well, five times seven is 35. And if you recall, 36 is divisible by 12

Â So five times seven is really -1 module of 12. 35 is minus

Â one module of twelve. But minus one module of 12 is basically the same as 11,

Â cuz I just add 12 to -1 and I get 11. And the next question is, how

Â much is 5 - 7 seven in the Z12? Well, 5-7 is -2.

Â -2 modulo 12, well, I just add 12 to -2 and I get 10. As a result,

Â we say that 5 - 7 is equal to 10. So again, this is just to make sure

Â everybody is comfortable with this notation of working in Z12. In other words, working in modulo 12.

Â Now, I'd just like to make a general statement that, in fact,

Â arithmetic in ZN, in other words, arithmetic modulo N works just as you

Â would expect. So, for example, all the laws that you know about addition and

Â multiplication work equally well in ZN. For example, the distributive law, X times

Â Y plus Z, is still gonna be equal to X times Y plus X times Z. So many of the

Â things that you know about arithmetic when working over the integers or in the reals,

Â will translate to working in, ZN, namely working modulo N.

Â So the next concept we need is what's called a greatest common divisor, or a GCD. And so suppose they

Â give you two integers X and Y. We say that the GCD of X and Y is basically the

Â greatest common divisor it's the largest number, the largest integer that divides

Â both X and Y. So for example, what is the GCD of 12 and 18?

Â Well the GCD is 6, because 6 divides both 12 and 18,

Â and it's the largest number that divides both 12 and 18.

Â Now there is an important fact about GCD's in particular, if I give you two numbers, two
integers X and Y, there will always exist

Â two other integers, I will call them A and B, such that if I look at a times X + B

Â times Y what I get is the GCD of X and Y. In other words the GCD of X and Y is a

Â linear combination of X and Y using the integers A and B. So far let us look at a

Â simple example, here, let's look at the GCD from before, so the integers for the

Â GCD would be 2 times 12 Minus 1 times 18. That's 24 minus 18,

Â which is equal to 6. So the integers A and B in this case would be 2 and -1

Â But this is just an example, and in fact, these integers, A and B will exist

Â for any integers, X and Y. Now not only do A and B exist, in fact there's a very

Â simple and efficient algorithm to find these integers, to find A and B. The

Â algorithm is what's called the extended Euclidean algorithm. This is actually one

Â of the prettiest algorithms from ancient Greek times, due to Euclid of course. I'm

Â not gonna show you how this algorithm works here, I. It's a fairly simple

Â algorithm. I'll just tell that in fact given X and Y, this algorithm will find A

Â and B in time roughly quadratic in the logarithms of X and Y. We'll come back to

Â that and discuss the, the performance of Euclid's algorithm I have a bit more

Â detail in just a minute. But, for now all we need to know is that A and B can

Â actually be found efficiently. Now, if the GCD of X and Y happens to be 1. In other

Â words, 1 is the largest integer that divides both X and Y, then we say that X

Â and Y are relatively prime. For example, the GCD of three and five, it's not

Â difficult to see that it hap, that happens to be 1, Because both 3 and 5 are

Â prime. The next topic we need to talk about is modulated inversion. So other

Â than rationals we know what the inverse of a number is. In other words if I give you

Â the number 2 the inverse of 2 is simply the fraction one half.

Â the qestion is what about inverses when we, we work module N. Well, so the inverse of

Â an element X in Z N is simply another element Y in Z N such that X times Y is

Â equal to 1 in Z N. In other words X times Y is equal to 1 modulo N. And this

Â number Y is denoted by X inverse. And it's not difficult to see that if, if Y exists,

Â then in fact it's unique. And as I said, we'll use X inverse to denote the inverse

Â of X. So let's look at a quick example. Suppose N is some odd integer, and I ask

Â you what is the inverse of 2 in ZN? So it's not too difficult to see that the

Â inverse of two in ZN in fact is N plus one over 2 and you can see that this is an

Â integer because N is odd, therefore, N+1 is even and, therefore, (N+1)/2

Â is in fact an integer and the range 1..N as required. Now why is (N+1)/2

Â the inverse of two? Well, let's just multiply the 2 so we do

Â 2 times (N+1) over 2 and what do we get? Well, that's simply equal to N+1

Â and N+1 is simply equal to 1 in ZN. So since their product is equal

Â to 1. We know that (N+1)/2 is the inverse of 2 in ZN.

Â Now we understand what a modular inverse is, the question is which elements actually have

Â an inverse in ZN? And so there's a very simple lemma that says that if for an

Â element X in ZN, that element has an inverse if and only if it is relatively

Â prime to the modulus N, to the number N. So I'll say that again. X and ZN is

Â invertible if and only if X is relatively prime to N. And let's quickly prove that.

Â It's actually fairly simple to see. So suppose a GCD of X and N happens to be

Â equal to one. So X is relatively prime to N. Well, by this property of GCD as we

Â know that there exists integers A and B. Such that A times X plus B times N is

Â equal to the GCD of X and N, which happens to be one. So A times X plus B times N is

Â equal to 1. Now we can actually take this equation here and, and us it reduce

Â it's modulo N. So what this means is that a times X is equal to one in Z, N. Once we

Â reduce this equation modulo N this term simply falls off because B times N is

Â divisible by N and therefore is 0 modulo N. But what we just showed is that

Â in fact X inverse is simply A in ZN. So because X is relatively prime to N, we

Â were able to show that X is invertible by actually building the inverse of X modulo N

Â Now what about the other direction? What happens if the GCD is greater than 1?

Â Then we want to show that there is no inverse. But that's actually very easy to

Â see because in this case, if you claim that A happens to be the inverse of X

Â modulo N, well, let's look at a<i>x; a<i>X we know should be equal to 1 modulo N</i></i>

Â But if the GCD(X,N) is bigger than 1, then the GCD(a<i>X,N)</i>

Â is bigger than one. But, if the GCD of A times X and N is bigger than 1,

Â then it's not possible that A<i>X is equal to 1. So A<i>X must also be</i></i>

Â bigger than 1, and therefore, A cannot be the inverse of X module N.

Â So this proves that, in fact, in, when the GCD is greater than 1, X cannot have an

Â inverse, because there is no A, such that A times X is equal to one modulo N

Â And this might be a bit confusing, so you might be best just to, do an example. So

Â let's look at, let's suppose that the GCD of X and N happens to be equal to 2.

Â I claim that X is therefore, is not invertible modular N. Well, why is that

Â true? Well, for all A, we know that A times X is gonna be even, is even. And the

Â reason we know that is because, well, 2 divides X and 2 divides N. Well, since

Â two divide X, 2 is also gonna divide A times X. And therefore, A times X must be

Â even. But what that means is that there's no way that A times X is equal to 1 modulo N

Â In particular, there's no way that A times X is equal to B times N + 1

Â This simply can't happen, this equality must not hold. Because this side

Â happens to be even, as we said. B times N for exactly the same reason is also even:

Â N is divisible by two; therefore B times N is also divisible by two. So therefore B

Â times N+1 is odd. And since even can't equal to odd, it's not possible that

Â A times X is equal to some multiple of N+1. And in particular this means

Â that A cannot be the inverse of X because A times X cannot be 1 mod N so X is not

Â invertible modular N. So now we have a complete understanding of what are the

Â invertible elements. Basically, we know that an element is invertible if and only

Â if it's relatively prime to N. And what I like about this proof is I would say this

Â is what's called a computer-science proof In the sense that not only does it prove

Â to you that the inverse exists; it also shows you how to efficiently calculate the

Â inverse. And the way we calculate the inverse, is basically by using this

Â extending decreasing algorithm. Define the numbers A and B. And once we found the

Â numbers A and B, we done because A is the inverse of X. And the numbers A and B can

Â be found very efficiently. So along the way I've also shown you an algorithm for

Â inverting elements, modulo N.

Â Okay. So bear with me, and let's introduce this little more notation. So we're gonna denote by ZN as the set of invertible elements in

Â Z N. In other words, ZN is the set of all elements in ZN such that GCD(X,N)=1

Â Okay. But I want you, again, to think of ZN as

Â basically those elements in ZN that have an inverse. So let's look at a few

Â examples. So let's start with a prime p. We know that of the integers from zero to

Â p-1, all of them are gonna be relatively primed to p except one

Â integer--namely, the integer 0. Zero is not relatively primed to P, because the

Â GCD(p,0)=0, not 1. So therefore, if p is a prime, the set ZP

Â is simply ZP minus 0, Which means that everything in Z<u>P is invertible</u>

Â except for 0. So if you like the size of ZP<i>, it's simply P-1. Now</i>

Â let's look at our favorite integer again. So why don't you tell me what is Z12

Â what is the set of invertible elements modulo 12?

Â