0:53

So, again, let's fix the primes P, and let's say that C is some element in ZP.

We'll say that X in ZP that satisfies X to the E is equal to C. We'll call such an X

the modular E-th root of C. So let's look at an example. We say that the cube root

of 7 in Z11 is equal to 6, because 6 cubed is equal to 216, which

happens to be 7 modulo 11. And therefore, the cube root of 7 modulo 11

is equal to 6. So let me ask you, what is the square root of 3 in Z11?

So the answer is 5 because 5 squared is equal to 25, which is 3 modulo 11.

And similarly, let me ask you, what is the cubed root of 1, modulo 11.

Well the cube root of 1 is simply 1, because one cubed is equal to 1, in Z11.

In fact that's true in modulo any prime. One thing I'd like to

point out is that these e'th roots don't always exist. For example, if I

asked you to compute the square root of 2 modulo 11, you'd have a problem,

because the square root of two simply doesn't exist modulo 11. So now that

we understand what an e'th root is, the next question is, when do these e'th roots

exist, and when we know that they do exist, can we actually compute them efficiently?

So, let's start with the easy case. The easy case is, when we want to

compute an e'th root of something, and it so happens that e is relatively prime to p-1.

In this case, c to the one over e always exists, and there's a very easy

algorithm to actually compute the e'th root of c and ZP. So let's see how this works.

So first, since e is relatively prime to p-1, we know that e has an inverse

modulo of p-1. So let's compute this inverse, and let's call it d.

So let's let d be the inverse of e modulo p-1. Then I claim that in fact c to the 1/e

is simply c to the d, modulo p. So if this equation holds then

first of all it proves that for all с in ZP the e'th root to c actually

exists. And moreover, it gives a very efficient algorithm to compute this e'th root to c,

simply by computing the inverse of e modulo p-1, and then raising

c to the power of that inverse. Okay? So we kill two birds in one stone. So let's

see why this equation holds. So first of all the fact that d times e is equal to

one mod p-1, what that means is there exists some integer k. Such that if I look

at d times e for that's basically gonna be k times p-1 plus 1. That's basically

what it means that d times e is equal to one modulo p-1. Well, so now we can

actually confirm that c to the d is a e'th root of C. Well, how do we

confirm that? Well, let's take C to the D, and raise it to the power of E. If in

fact, c to the d is an e'th root of c, when we raise it to the power of e;

we're supposed to get c back. So let's see why that's true. Well, that's simply equal

to c times d to the e, and c times d to the e, well, by definition, is equal to c

to the power of k times p-1 plus 1 Well, using the laws of

exponentiation, we can write this as c to the power of p-1 to the power of k times c.

All I did is I distributed the exponentiation using the standard laws of exponentiation.

Now what do we know about c to the p-1? Since c lives in ZP

by Fermat's theorem we know that c to the p-1 is equal to 1, in ZP.

1 to the k is also equal to 1 and as a result, this is simply equal to c in ZP,

which is exactly what we needed to prove that c to the d is an e'th root of c.

Okay. So this is what I call the easy case. In fact, the e'th root always exists

when e is relatively prime to p-1. And it's very easy to compute it

simply by using this formula here. Now let's turn to the less easy case. So the

less easy case is when e is not relatively prime to p-1. And the canonical example

here is when e is equal to 2. So now suppose we want to compute square roots of

c in ZP. So if p is an odd prime, and in fact we are going to focus on odd primes

from now on, then in fact p-1 is going to be even. Which means that two are divided

p-1, and indeed the gcd(2,p-1) is not equal to 1, So this is not the easy case.

So the algorithm that we just saw on the previous slide is not gonna work when

we want to compute square roots modulo an odd prime.

So when we work modulo odd prime, the squaring function is actually a 2-to-1 function. Namely, it maps X and

minus X to the same value. It matched both of them to X squared. And as a result, we

say that this function is a 2-to-1 function. So here's a simple example.

Let's look at what happens when we compute squares modulo eleven. So you can see that

1 and -1 modulo 11 both map to 1. 2 and -2 both map to 4.

3 and -3 both map to 9, and so on and so forth, So you can

see that it's a 2-to-1 map. So, in fact, these elements here, 1, 4,

9, 5, 3, all are gonna have square roots. For example, the square root

of 4 is simply gonna be 2 and 9. And I claim that, in fact, none of the

other elements of Z11 are gonna have a square root. And that motivates this

definition to say that an element x in ZP, we're gonna say, is called a quadratic

residue. If in fact, it has a square root in ZP. Okay, and if it doesn't have a

square root, we'll say that it's a non quadratic residue. For example modulo 11

4 is going to be a quadratic residue, 9 is a quadratic residue, 5

is a quadratic residue, 3 is a quadratic residue, and, of course, 1 is

a quadratic residue. So let me ask you, if p is an odd prime, what do you think is

the number of quadratic residues in ZP? And I'll give you a hint; the squaring

function is a 2-to-1 map, which means that half the elements in ZP can't have a

pre-image under this map. So the number of quadratic residues is simply (p-1)/2 + 1

And the reason that's true is because we know that exactly half

the elements in ZP are gonna be quadratic residues, Because of the fact

that the squaring function is a 2-to-1 map. So there can be, at most (p-1)/2

elements in the image of that map. So half the elements in ZP are

quadratic residues, And then, in ZP, there's also zero. We also have to account

for zero. Zero is always a quadratic residue, 'cause zero squared is equal to

zero. So overall, we get (p-1)/2 quadratic residues in ZP<i>, plus 1,</i>

the zero element, which is a quadratic residue in ZP. So overall, in ZP, there

are (p-1)/2 + 1 quadratic residues. Okay, so the main points to

remember is that roughly half the elements have a square root and the other half does

not have a square root. I wanna emphasize that this is very different from the easy

case, where e was relatively prime to p-1. If you remember in the easy

case, every element in ZP had an e'th root. When e is not relatively prime to p-1,

that's no longer the case, and in particular in the case of e equals 2,

only half of the elements in ZP have a square root. Well, so the natural

question then is, can we given an element x that's in ZP<i>, can we tell whether it has</i>

a square root or not? So Euler did some important work on that too and in fact, he

came up with a very clean criteria to test exactly which elements are quadratic

residues and which are not. And in particular he said that x and ZP is a

quadratic residue if and only if x to the power of (p-1)/2 is equal to 1 modulo p.

Okay, very, very elegant and very simple condition. Let's see a simple

example in Z11, so when we work mod 11. So here I compute it at the 5th

power of all the elements in 11 for you, and you can see that this symbol,

this X to the (p-1)/2, is always either one or minus one, and it's

one precisely at the quadratic residues--so 1, 3, 4, 5, and 9.

Okay, those are the quadratic residues, and the other elements are not

quadratic residues. Here, I'll circle them in green. These are the elements that do

not have a square root when we work modulo 11. One thing I'd like to point out

is, in fact, if we take an x that's not equal to 0, and we look at x to the (p-1)/2

Well, we can write that as the square root of x to the p-1

The kind of, the half bubbles out, and this is simply the square

root of x to the p-1. Well, x to the p-1 by Fermat's theorem, is 1.

So, x to the (p-1)/2 is simply a square root of 1, which must be 1 or -1.

So what this proves is that really this exponentiation here must

output 1 or -1, and we actually saw that happening here. It outputs 1

when x is a quadratic residue, and it outputs -1 when x is not a

quadratic residue. This is not a particularly difficult proof, but I'm not

going to show it to you here. It's in the reference that I point to you at the end

of the module. And just for completeness, I'll mention that this value, x to the (p-1)/2

has a name, it's called the Legendre's symbol of x over p.

And as we said, this for elements in ZP the symbol is either 1 or -1

depending on the quadratic residuosity of x. Now, the sad thing about Euler's

Theorem is that it's not constructive. Even though it's a very, very cute theorem,

it tells us exactly which elements are quadratic residues and which

aren't, this theorem doesn't do it constructively, in the sense that if we

want to compute the square roots of a quadratic residue, the theorem doesn't

actually tell us how to do that. And in fact, even if you look at the proof, the

proof is by an existential argument. So it proves that the square roots exists, but

it doesn't show us how to compute the square root when we want it.

So the next question is then how do we compute square roots modulo primes. So it turns out

that's actually not so hard and, again, it breaks up into two cases. The first case

is when p is equal to 3 modulo 4 in, which case, it's really easy to

compute the square root and I'll just tell you there's a simple formula. The square

root of c in this case is simply c to the power of (p+1)/4.

You'll notice that because p is equal to 3 modulo 4, p+1 is necessarily,

p+1 is equal to 0 modulo 4. Which means that p+1 is divisible by

4, and therefore (p+1)/4 is an integer. And that's exactly what allows

us to compute this exponentiation, and I claim that, that actually gives us the

square root of c. Very simple formula, that directly gives us the square root of c.

So let's verify that that's actually true.

Well I'll take c to the power of (p+1)/4 and square that.

And if, in fact, if c to the (p+1)/4 is the square root of c, when I square it, I should get c.

So let's see what happens. So first of all, by laws of exponentiation, this is simply equal to c

to the power of (p+1)/2. And that I can write as c to the power of (p-1)/2 times c

Okay, again, this is basically, I took, one-half, and moved it

out of the exponentiation. Now, what do we know about c to the power of (p-1)/2 ?

Since c is a quadratic residue, we know that c to the power of (p-1)/2 is 1.

And therefore, this is really equal to one times c, which is c in

ZP as we wanted to show. Okay. So this basically proves that c to the power of (p+1)/4

is the square root of c, at least in the case when p is equal to 3 modulo 4.

Now you should ask me, well, what about the case when p is equal to 1 mod 4 ?

In that case, this formula doesn't even make sense. Because (p+1)/4

this exponent here, (p+1)/4 is gonna be a rational fraction, and I don't

know how to raise, c to the power of a rational fraction. Nevertheless, it turns

out that even in the case where p is equal to 1 mod 4; we can efficiently find

square roots, although it's a little bit harder. And in particular, we don't have a

deterministic algorithm to do it. We have to use a randomized algorithm to do it.

13:46

But this randomized algorithm will actually find the square root of x mod p,

very efficiently. I guess I should mention that if someone could prove that the

extended Riemann hypothesis--this is some deep hypothesis of analytic number theory. If

someone could prove that, that hypothesis is true, in fact, it would give a

deterministic algorithm for computing square roots even when p is equal to 1 modulo 4.

So the reason I like to mention that is because you notice that as

soon as you put the computational lens on something--for example, I ask you to

compute the square roots of a number x modulo p. Coming up with an algorithm

already requires extremely, extremely deep results in mathematics some of which are

not even known to be true today. So as things stand today, we simply don't have a

deterministic algorithm to compute square roots where p is 1 mod 4. But as I

said, we have good randomized algorithms, and this problem is considered easy.

Essentially, it boils down to a few exponentiations. And as a result, as we'll

see, the running time of computing square roots essentially is cubic in the number

of bits of p. So excellence. And now we know how to compute square roots mod p,

and so now we can talk about solving quadratic equations modulo p. So suppose

I give you a quadratic equation and I asked you to find a solution of this

quadratic equation in ZP. Well so now I claim that you know how to solve it. The

way you would solve it is basically you would use the high school formula for

solving quadratic equations, you know. So the solution is minus b plus minus the

square root of b squared minus 4ac over 2a. And I claim that you know how to

compute all the elements in this formula. So you know how to compute the inverse of 2a.

So you can divide by 2a. That's done using the extended Euclidean algorithm.

And you know how to complete a square root of b squared minus 4ac, using one of

the square root algorithms from the previous slide. And of course the formula

will only be solvable if the square root actually exists in ZP. So that's cool. So

now, you guys know how to solve quadratic equations in ZP. So now, the next obvious

question is what about computing these roots, modulo composites rather than

modulo primes. So we can ask exactly the same questions that we asked before. So

when does the e'th root modulo N exist? And if we know that it exists, can we

actually compute it efficiently? And here, the problem is much, much, much harder.

And in fact it turns out that, for all we know, computing e'th roots modular

composites is in fact as hard as factoring that composite. Now, for a general e, this

is actually not known to be true, but the best algorithm that we have for computing

e'th roots modulo N requires us to factor the modulus. And once we factor the

modulus, then it's actually easier to compute e'th roots modulo each of the

prime factors. And we can combine all the e'th roots together to get the e'th roots

modulo the composite N. So it's a very interesting case, where computing e'th

root modulo prime was very easy. In fact, for many e's, it was very easy. But

computing e'th root modulo composite is much, much, much harder and, in fact,

requires the factorization of N. So that's all I wanted to tell you about e'th roots.

In the next segment, we're gonna turn to modular algorithms and we're gonna talk

about addition and multiplication and exponentiation algorithms, modulo primes and composites.