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?