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*, if we look at a
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.
Okay, it's basically the smallest power
that causes the power of G to be equal to
one. And it's very easy to see that this
equality here basically if we look at all
the powers of G and we look at one, G, G
squared, G cubed and so on and so forth up
until we get to G to the order of G minus
one. And then if we look at the order of G
to the order of G. This thing is simply
going to be equal to one, by definition.
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.
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.
Okay so we say that this is a
generalization of Fermat's theorem and
in fact as we'll see this Euler's
theorem is the basis of the RSA crypto
system. So I stop here and we continue
with modular quadratic equations in the
next segment.