-
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.