Okay. So now, in this lecture, you'll finally
understand Shore's Algorithm for factoring integers.
So, and remember, what we did in the last lecture, we talked about this primitive
called period finding. And so today, we'll see how to use this,
this primitive in order to factor integers.
So, remember, what period finding does, it, you are given a function f from some
domain, like the integers from zero to N - one.
It's a function from that, from, from integers mod N to, to just some set.
And this function has a property that it's periodic with period r.
Let f(x) = f (x) + r. Your challenge is to find r.
So, we saw that this is a difficult task to do classically.
But under that, quantumly you can do this very efficiently and the way you do this
is you have a circuit which looks very much like the one we saw for Simon's
algorithm so you have a Quantum Fourier transform modem followed by the circuit of
computer. Followed by another Quantum Fourier
transform modem and then you measure and this, the result of this measurement gives
you allows you to reconstruct what r is, okay?
So, again, remember, remember how we, how we said in the case of Simon's algorithm,
the quantum circuit could be seen as, as, as a virtual two slit, double slit
experiment. So, in the case of period finding, the
circuit can be seen as a virtual multiple slit experiment, because after you do this
Quantum Fourier transform you're in a, superposition over all the numbers a mod
N. And then, then when you compute U, or
compute f, you get summation over a of e modem, followed by f(e) modem, right?
So, this was sum over all a from zero to N -one of a, a out here and zero out here
and then after you do the compute f, you'll get sum over all a equal to zero to
N - one and this contains a and this contains f(a).
And so, now, when you, when you measure this, you will see some value of, you
know, f, f(a) and then, in the first register you have a superposition over a,
a + r, a + 2r, and so on. So, these are you multiple slits that
you've carved virtual slits. And then, when you do a Quantum Fourier
transform, you get interference button which, which tells you, you know, because,
because these slits are r apart, you get interference at some quantity related to
r. And so, using that, you can reconstruct
what r was, the period was. Okay, so now, how do we use this to factor
a number? So, remember what the factoring problem
is. You're given some number N and you want to
write it in the form in its prime factors, p1 to the e1, p2 to the e2, pk to the ek.
Right now, if N is a, you know, if' N was a thousand digit number, then classically,
this is very hard to factor. Of course, the most naive algorithm would
just try all prime factors until you, until you find one.
But then, if N were, in the hard cases where N was a product of two primes, P
times Q and say that each of P and Q is a 500 digit prime number.
So now, in this case, trial division is going to take way too long.
It'll take ten to the, the, ten^500 possible factors, divisors to try and
that's just, that's just hopeless. Now, the fastest algorithms we know
classically are much better than this. But this still take exponential time.
And so, this is why the factoring problem is considered cryptographically hard.
And that's the basis of the RSA cryptic system.
Okay. So, for the purposes of this lecture, just
to make things conceptually simple, I'm going to assume N is of this form, it's of
the form P times Q, where P and Q are two odd primes.
But, but, of course, everything I say is going to be completely general and so
it'll, it's going to work for any N, you know, any compositor, which is, let's,
let's say, any odd compositor. Okay.
So, generally, more, more generally, if, if the number of digits or the number of
bits, the length of number is little n, right?
Then, if, if little n is the number of, number of bits that it takes to write out
capital N, then capital N is about, two to the little n.
And a classical algorithm, the best classical algorithms take time which is
exponential in square root of N, okay? By contrast, a quantum algorithm for, for
computing, for finding the, the factors of N is going to run, so this is, this is,
this is best classical algorithm and by contrast, a quantum algorithm for
computing, for finding these, the prime factorization of, of N, we'll run in time
which is polynomial, say, order N^3 Although we can, we can improve it, the,
the, the exponent might be squared or using certain tricks we can improve it
even further. But, but, the most important thing here is
that it goes from exponential time to polynomial time.
So now, in order to understand how this algorithm works, we are going to have to
understand some, you know, we're, we're going to have to understand some very
elementary number theory, theoretic facts, which I'll now explain to you.
But to, to understand these, these, these simple facts, you, you'll, of course, need
some background in what's called Modular Arithmetic.
I, I hope you already have this background.
If not, let me point you to the, to the, to some resources online that will, that
will, help you understand that. So, what's meant by Modular Arithmetic?
We say that two numbers, A and B are congruent mod N, if A - B is divisible by
N. So, think of Modular Arithmetic as what
happens when you, when you have numbers around a clock face.
So, they are counting modular twelve. So, for example, if, if the time is
fifteen o'clock, well, you don't ever think of fifteen o'clock, you subtract off
twelve and you get a number always between zero and, well, okay, so if you're, if
you're really doing it mod twelve then you don't, you know, you call twelve, zero so
you, your, your numbers are always zero, one, two, three up to eleven, okay?
Now if you don't already know about Modular Arithmetic, let me refer to you
some, an online resource. There's a book on algorithms that you
know, I've posted on my webpage. This is, you know, this is the, an almost
final copy. This was a pre-copy edited version of the
book. And the first chapter is, you know, is on
Modular Arithmetic. The second half of the second chapter is
on the Fast Fourier transform. And chapter ten is on quantum factoring
so, so, you have this, you know, you have this resource available if you, if you
need to look up any of the background for, for Modular Arithmetic or some of these
later, later topics. Okay.
So, so now, assuming everybody knows about Modular Arithmetic, let's, let's just go
ahead and say, let's, let's work with an example, let's say that let's say that we
have N = 21. This is the number that we are trying to
factor and we are pretending that N is very large, 21 is too large for us to deal
with by any of our standard methods. So, what are we going to do?
Well, it turns out that okay so, so normally, if you, if you were looking at
the square root of one you know, in regular arithmetic, this would be plus or
minus one. And, of course, indeed, that's, that's
also through mod N. So, for example, you have one^2 is
congruent to one mod 21. And -one, which is also twenty when you,
when you square it, you'll also get, one mod 21, okay?
So, so, you know, -one is the same thing as twenty mod 21 and if you, if you go
ahead and square twenty, you will get 400 and, and you should check that 400 is
congruent to one mod 21. Of course, you don't need to do this
because, you know twenty is-1 but, okay. Now, it turns out that mod N, when N is a
composite, these are not the only two numbers that square to one mod N.
So, there is another square root of, of, of 21.
And that happens to be eight, because eight^2, which is 64, I can see when you,
you use mod 21, 21 times three is 63 and so, the reminder is one.
So, eight^2 is 64, which is one mod 21, okay?
So, I claim that once you locate such a nontrivial, we, we call this a nontrivial
square root of one mod 21. Once you have such a, such a nontrivial
square root, you can use it to factor 21 because, because now, what we can claim is
the G, the GCD eight + one and 21, the greatest common divisor is, is going to
give you a nontrivial square root and the GCD of eight - one and 21 will also give
you a nontrivial square root of, nontrivial factor of 21.
Okay. So, what's the greatest common divisor of
eight + one which is nine and 21? Well, the greatest common divisor of these
two numbers is, is three, which is indeed one of the factors of 21.
And this number is, the seven, and the GCD of seven and 21 is, is seven, so, so we
manage to find, we manage to factorize 21 just by computing this nontrivial square
root of one mod 21. Now, of course, there's another, there
should be another nontrivial square root because they come in, they come in pairs,
and that would be -eight. -Eight is, is the same as, what's -eight
mod 21? It's, it's -eight + 21, which is thirteen.
So, I claim -eight^2 which is thirteen^2 is also common to one mod 21.
That's a 169 and you should, you should check that 168 is, is divisible by 21.
And so, you could have done the same thing with thirteen.
You could have said, GCD of thirteen plus one and 21 is going to be nontrivial.
So, this was14, and indeed the GCD is, the greatest divisor is seven.
Also, the GCD of thirteen - one and 21. Well, what's this?
This is twelve, the GCD is three, okay, so, you recover the factors of N, okay.
So, so, what's going on here? Well, what's going on here is this general
principle. If x is a nontrivial square root of one
mod N, ten the GCD of x + one and N, N is the GCD of x - one and N give you
nontrivial factors of N. How do you prove this?
Well, let's see. X is a nontrivial square root of one mod
N, meaning x is not congruent to plus or minus one mod N.
But it's the square root of one mod N, so meaning, x^2 is congruent to one mode N.
What's another way of saying this? Meaning, x^2 - one is congruent to zero
mod N, which means that N divides x^2 - one.
Okay, but then N divides (x + one) (x - one).
Okay, but, but what do we with this? Well, remember also, x is not congruent to
plus or minus one mod N, which is the same thing assigned by the same kind of
reasoning that N does not divide. X plus or minus one.
Okay, so, so now, N divides x + one times x - one, but N does not divide x + one and
N does not divide x - one. So, how could it be?
How could it be that N divides this product but it doesn't divide either one?
Okay. Well, only way it could be is if some of
the prime factors of N divide x - one and some of them divide x - one.
So now, what this tells us is that the greatest common divisor of x + one and N
must, must be a part of N, but [unknown] is saying, it's just a product of two
primes. So, this must be the smallest of the prime
factors. And the greatest common divisor of x-1 and
N must be less than other prime factor, alright?
So, for example, this might give us P, this might give us Q, and that's how we
can factor.