Fermat and Euler (18 min)

I'll copy them over to "English"

In the previous segment, we talked about modulo inversion,

and we said that Euclid's algorithm gives us

an efficient method to find the inverse of an element modulo m.

In this segment we are going to forward through time

and we're going to move to the 17th and 18th century

and we're going to talk about Fermat's and Euler's contributions.

Before that, let's do a quick review of what we discussed in the previous segment.

So as usual, we're going to let N denote a positive integer,

and let's just say that N happens to be a n-bit integer.

In other words, it's between 2^n and 2^(n+1).

As usual we are going to let p denote a prime.

Now we said that Z sub n is the set of integers from 0 to N - 1.

And we said that we can add and multiply elements in the set modulo N.

We also said the Z_N* is basically the set of invertible elements

in Z_N and we proved the 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 Z_N.

And we said that the running time of this algorithm is basically of order n-squared

where again n is the number of bits of the number capital N.

So as I said, now we're gonna move from Greek times all the way to

the 17th century and talk about Fermat.

So Fermat stated a number of important theorems.

The one that I want to show you here is the following:

So suppose I give you a prime "p".

Then in fact, for any element x in in Z_p*, it so happens

that if I look at x and raise it to the power p-1,

I'm gonna get 1 in Z_p.

So let's look at a quick example.

Suppose I set the number p to be 5

and I look at 3 to the power of p-1 - in other words 3 to the power of 4 -

3^4 is 81, which in fact is 1 modulo 5.

The example satisfies Fermat's theorem.

Interestingly Fermat actually didn't prove this theorem himself.

The proof actually waited until Euler, who proved it almost a 100 years later

and in fact he proved a much more general version of this theorem.

So lets look at a simple application of Fermat's theorem.

Suppose I look at an element x in Z_p*,

and I want to remind you here that p must be a prime.

Well, then what do we know? We know that x^(p-1) = 1.

Well, we can write x^(p-1) as x*x^(p-2).

Well, so now we know that x*x^(p-2) happens to be equal to 1,

and what that says is that really the inverse of x modulo p

is simply x^(p-2).

So this gives us another algorithm for finding the inverse of x modulo a prime:

simply raise x the power of p-2

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 2 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 exponentiation

- 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^3(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 going to be making extensive use of it

in the next couple of weeks.

So let me show you a quick and simple application of Fermat's theorem.

Suppose we wanted to generate a large random prime.

Say our prime needed to be 1000 bits or so.

So the prime we're looking for is on the order of 2^1024, say.

So here is 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 2,

we would test whether 2^(p-1) equals 1 in Z_p.

If the answer is no, 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 1

and we try another prime.

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 2^-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-bit integers,

then, well, there is the set of primes, when we 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 is 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 and one here, and so on -

as we choose random integers,

the probability that we fall into this 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.

And 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 a last point, I'll say that

you might be wondering how many times this iteration

has to repeat until we actually find a prime.

And that's actually a classic result,

it's called the Prime Number Theorem

which says that

after a few hundred iterations

we'll find a prime with high probability.

So expectation, one would expect

a few hundred iterations, no more.

Now that we understand Fermat's theorem,

the next thing I want to talk about is

what's called the structure of (Z_p)*.

So here we're going to move a hundred years into the future,

into the 18th century,

and look at the work of Euler.

And one of the first things Euler showed

is, in modern language,

is that (Z_p)* is what's called a cyclic group.

So what does it mean that (Z_p)* is a cyclic group?

What it means is:

there exists some element g in (Z_p)*

such that if we take g and raise it to a bunch of powers,

g, g^2, g^3, g^4 and so on and so forth

up until we reach g^(p-2)

- notice there is no point of going beyond g^(p-2)

because g^(p-1) by Fermat's theorem is equal to 1,

so then we will cycle back to 1

if we go back to g^(p-1),

then g^p will be equal to g,

g^(p+1) will be equal to g^2, 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^(p-2).

And what Euler showed is

that in fact there is an element g

such that if we look at all of its powers,

all of its powers span the entire group (Z_p)*.

Powers of g give us all the elements in (Z_p)*.

An element of this type is called a generator.

So g would be said to be a generator of (Z_p)*.

So let's look at a quick example.

Let's look for example at p=7,

and let's look at all the powers of 3,

which are 3^2, 3^3, 3^4, 3^5.

3^6 already, we know, is equal to 1 modulo 7 by Fermat's theorem,

so there's no point in looking at 3^6:

we know we would just get 1.

So here I calculated all of these powers for you,

and I wrote them out,

and you see that in fact, we get all the numbers in (Z_7)*.

In other words, we get 1, 2, 3, 4, 5 and 6.

So we would say that 3 is a generator of (Z_7)*.

Now I should point out that not every element is a generator.

For example, if we look at all the powers of 2,

well, that's not going to generate the entire group.

In particular, if we look at 2^0, we get 1.

2^1, we get 2.

2^2 is 4, and 2^3 is 8, which is 1 modulo 7.

So we cycled back.

And then 2^4 would be 2,

2^5 would be 4, and so on and so forth.

So if we look at the powers of 2,

we just get 1, 2 and 4.

We don't get the whole group.

And therefore we say that 2 is not a generator of (Z_7)*.

Now again, something that we'll use very often

is, given an element g of (Z_p)*,

if we look at the set of all powers of g,

the resulting set is going to be called

the group generated by g.

OK? 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 going to call all these powers of g

the group generated by g.

In fact, there's this notation which I don't use very often:

"" to denote this group that's generated by g.

And then we call the order of g in (Z_p)*,

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)*

is the size of this group.

But another way to think about that

is basically, it's the smallest integer a

such that g^a is equal to 1 in Z_p.

OK? It's basically the smallest power

that causes a power of g to be equal to 1.

And it's very easy to see that

this equality here,

basically if we look at all the powers of g

- we look at 1, g, g^2, g^3 and so on and so forth,

up until we get to g to the order of g minus 1,

and then if we look at g to the order of g,

this thing is simply going to be equal to 1 by definition.

OK? So there's no point in looking into 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 1 in Z_p.

So I hope this is clear,

although it might take a little lateral thinking

to absorb all this notation.

But in the meantime, let's look at a few examples.

So again, let's fix our prime to be 7.

And let's look at the order of a number of elements.

So what is the order of 3 modulo 7?

Well, we're asking: what is the size of the group

that 3 generates modulo 7?

Well, we said that 3 is a generator of (Z_7)*,

so it generates all of (Z_7)*.

There are 6 elements in (Z_7)*.

And therefore we say that the order of 3 is equal to 6.

Similarly I can ask:

well, what is the order of 2 modulo 7?

And in fact, we already saw the answer.

So, let's - I'll ask you, what is the order of 2 modulo 7

and see if you can figure out what this answer is.

So the answer is 3.

And again, the reason is,

if we look at the set of powers of 2 modulo 7,

well, we have 1, 2, 2^2,

and then 2^3 that's already equal to 1,

so this is the entire set of powers of 2 modulo 7.

There are only three of them.

And therefore, the order of 2 modulo 7 is exactly 3.

Now let me ask you a trick question:

What's the order of 1 modulo 7?

Well, the answer is 1,

because if you look at the group that's generated by 1,

well, there's only one number in that group,

namely the number 1.

If I raise 1 to a whole bunch of powers,

I'm always going to get 1,

and therefore the order of 1 modulo 7,

in fact, the order of 1 modulo any prime,

is always going to be 1.

Now, there's an important theorem of Lagrange that

- actually, this is a very very special case of what I was telling here.

But Lagrange'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[s], you see

6 divides 7 minus 1. 6 divides 6.

And similarly, 3 divides 7-1, namely again, 3 divides 6.

But this is very general.

The order is always going to be a factor of p-1.

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 fact,

and so Fermat's theorem really in some sense

follows directly from Lagrange's theorem.

Lagrange, by the way, did this work in the 19th century,

so we can already see how we're making progress through time.

We started in Greek times,

and already we ended up in the 19th century.

And I can tell you that more advanced crypto

actually uses 20th-century math very extensively.

Now that we understand the structure of (Z_p)*,

let's generalize that to composites

and look at the structure of (Z_N)*.

So what I want to show you here is what's called Euler's theorem,

which is a direct generalization of Fermat's theorem.

So Euler defined the following function:

So given an integer N,

we define what's called the phi function, phi of N,

to be basically the size of the set (Z_N)*.

This is sometimes called "Euler's phi function".

The size of the set (Z_N)*.

So for example, we already looked at (Z_12)*.

We said that (Z_12)* contains these four elements

1, 5, 7 and 11,

and therefore we say that phi of 12 is simply the number of 4.

So let me ask you as a puzzle:

What is phi of p?

It'll basically be the size of (Z_P)*.

And so in fact we said

that (Z_P)* contains all of Z_P

except for the number zero,

and therefore phi of p for any prime p

is going to be p-1.

Now there's a special case which I'm going to state here

we're going to 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 1.

Let me just show you why that's true.

Basically, N is the size of Z_N.

And now we need to remove all the elements

that are not relatively prime to N.

Well, how can an element not be relatively prime to N?

It's got to be divisible by p,

or it's got to be divisible by q.

Well, how many elements between zero and N-1

are 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'll notice we subtracted 0 twice,

because 0 is divisible both by p and q.

And therefore we add 1,

just to make sure we subtract 0 only once.

And so it's not difficult to see

that phi of N is N minus p minus q plus 1.

And another way of writing that is simply:

p minus 1, times q minus 1.

OK? So this is a fact that we will use

later on when we will 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)*,

in fact it so happens that

x to the power of phi of N is equal to 1 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 of p is equal to p-1,

and in other words,

if N were prime, we would simply write p-1 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 5 to the power of phi of 12.

So 5 is an element of (Z_12)*.

If we raise it to the power of phi of 12,

we should be getting 1.

Well, we know that phi of 12 is 4,

so we're raising 5 to the power of 4.

5 to the power of 4 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.

And in fact, it's not difficult to prove Euler's theorem.

And in fact I tell you that Euler's theorem

is also a very special case

of Lagrange's general theorem.

OK. So we said 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 cryptosystem.

So I'll stop here,

and we'll continue with modular quadratic equations

in the next segment.