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.
