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.