Cryptography is an indispensable tool for protecting information in computer systems. In this course you will learn the inner workings of cryptographic systems and how to correctly use them in real-world applications. The course begins with a detailed discussion of how two parties who have a shared secret key can communicate securely when a powerful adversary eavesdrops and tampers with traffic. We will examine many deployed protocols and analyze mistakes in existing systems. The second half of the course discusses public-key techniques that let two parties generate a shared secret key. Throughout the course participants will be exposed to many exciting open problems in the field and work on fun (optional) programming projects. In a second course (Crypto II) we will cover more advanced cryptographic tasks such as zero-knowledge, privacy mechanisms, and other forms of encryption.
Modular e'th Roots
Loading...
From the course by Stanford University
Cryptography I
2436 ratings
From the lesson
Basic Key Exchange
Week 5. This week's topic is basic key exchange: how to setup a secret key between two parties. For now we only consider protocols secure against eavesdropping. This question motivates the main concepts of public key cryptography, but before we build public-key systems we need to take a brief detour and cover a few basic concepts from computational number theory. We will start with algorithms dating back to antiquity (Euclid) and work our way up to Fermat, Euler, and Legendre. We will also mention in passing a few useful concepts from 20th century math. Next week we will put our hard work from this week to good use and construct several public key encryption systems.
Meet the Instructors
Dan BonehProfessor
Computer Science
In the previous segment, we talked about how to solve modular linear equations.
In this segment, we're gonna talk about how to solve modular quadratic equations.
And more generally, we're gonna talk about how to compute modular e'th roots. As I said,
now we know how to solve linear equations simply by using an inversion algorithm to
compute a inverse and then multiplying the result by minus B. So the question is
what about higher degree polynomials and in particular we are interested in
solving, polynomials modulo primes. So solving polynomials in ZP, but polynomials
particularly of the form x squared - c or y cubed - c or z to the 37 - c, all in ZP.
So solving this polynomial, for example, involved computing the square root of C.
Solving this polynomial involves computing the cube root of C.
Solving this polynomial involves computing the thirty-seventh root of C. And so on.
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.
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.
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2019 Coursera Inc. All rights reserved.
