Okay, but, but now remember N is a very
large number.
Right?
It's a 1000 digit number.
We are still looking for a needle in a
haystack, because we are looking for this
non-trivial square root of one mod n.
There are only two of them, two out of
these ten to the 1000 numbers.
What chance we have of finding them?
So this is where we use another kind of
approach.
So let's again do this by example, and
then we'll see the general principle.
So let's pick a number mod, mod, mod 21.
So let's say we pick a number like two.
And, now we look at, we look at the powers
of two, okay?
So, let's look at two^0 = one.
Two^1 = two.
Two^2 =
Four.
Again, looking at everything mod 21,
right?
There is always mod the number we are
trying to factor.
>> How about two cubed?
It's eight mod 21.
Two^4 = sixteen mod 21.
Two^5, Well it's 32 but what's 32?
It's, 32 is eleven mod 21. two^6 is,
eleven two = 22.
What's 22?
It's one mod 21.
Okay.
So now is it significant that two^6 = one
mod 21?
Well, yes it is because what this tells
us, since two^6 is congruent to one mod
21.
What this tells us is that if we take two
cubed and we square it, this is two^6
which is one mod 21, so this means that
two cubed.
This is a nontrivial square root of one
mod 21, right?
But what's two cubed?
That's eight.
Remember?
That was the number that we found which
was a nontrivial square root of, of, of
one mod 21.
So we have found eight squared is
congruent to one mod 21.
Okay.
So now, what's the general principle
underlying in all this?
So this, here's the general lemma which I
won't prove but if you, if you wish to
understand how to prove it you can, you
can look up the reference that I gave.
So, what it says is, that this happens in
complete generality.
So let N be an odd composite.
Now N And, and let's say that N has at
least two distinct prime, prime factors.
You know, that's the case that we are
interested in because now we, we want to
factorize N.
And it says, suppose we pick x uniformly
random between zero and N - one.
And which is relatively prime to N.
Because if it's not relative, so we pick
an x uniformly random between zero and N -
one.
If GCD of x and N is not equal to one,
then we're already done because we have
managed to factorize it.
So, but if GCD of x and N is one which is
the usual case, then with probability at
least a half.
The order x mod N is even and x^r/2 is a
non trivial square root of one whatever.
What do you mean by this?
So what it means, what we mean by this is,
it can accept random mod N.
So this was like picking two mod 21.
And now you find the minimum non-zero
minimum positive power of x mod N.
So find what power you must raise it to so
that you get one.
Okay.
So this r is called the order.
Of x mod N.
So now, what this lemma is telling us is,
if he picks, picks x at random, then half
the time we've been the good case where r
is even and x^R/2 is not congruent to + or
-one mod N.
So if you call this x^r/2y, then we have
the case that y is not congruent to + or
-one mod N but y squared, which is x^r is
congruent to one mod N.
So we found our nontrivial square root of
one mod N and we can use it to factor, as
we saw before.
Okay.
But, this still leaves us with a problem.
How do we actually compute this?
You know, we, we, we, we found, you know
we pick an x at random.
It's going to work with probability half,
that's great.
But how do we find this order of x?
Because order of x can be very, very
large.
It can be you know comparable in size to
N.
But N, remember, is a thousand bit,
thousand digit number.
So, so N is like ten to the 1000.
So, the order might be this huge number
and we can't, we can't be raising x to
every power.
So, what's the short cut?
Okay so, so let's go back and let's, let's
look at what we do.
So, so let's make up a, a, you know so
we've picked this number, number x = two.
We are working, we have N = 21.
And now let's, let's just build up a
table.
So, so let's, Let's build a, build a table
where, where we have a number A and here
we have x^a mod N.
Okay.
So think of, think of this as f of a.
Okay, so when we have a = zero, what's,
what's x to the zero mod, mod 21?
It's one.
A
= one.
What's two^1 mod, mod 21?
It's two.
Equal to two and four, three, eight, four,
sixteen.
Five.
Okay, what's two to the five?
It's 32.
32 mod 21 = eleven.
Six, one remember that was the order two
mod 21. seven now we start repeating.
Two, eight, four, nine, eight ten,
sixteen, eleven.
Sixteen^32, we get back to eleven.
Twelve, we're back to one.
Thirteen, two, fourteen, four.
Okay you see the pattern right?
You get this periodic function.
Okay.
What are we trying to find?
We are trying to find the order.
What's the order?
Well, it's a period of this periodic
function.
So what should we do?
Well, so here's a function that we can
compute efficiently.
What we should do is period finding,
right?
So what do we do in period finding?
We set up a superposition.
We go into a sum over all a.
And if you, if you do this over a range of
M, 1/ square root M.
A = zero^M-1.
And then, we are in, we are in this
superposition over a, of a, f(a) and then
we measure this register.
What happens when we measure this
register?
Let's say we get the value four.
So we measure this register and we get the
value four.
Now what's the, what's our first register
look like?
Well, it's in a superposition over this.
Over everything where the second register'
is four.
So that, ...
>> That.
So now we get this periodic superposition.
We have superposition over two, eight,
fourteen, right?
It's periodic with period form.
And now when we do a fourier transform
again, it shows up the period, right?
Once we have the period, we find a
nontrivial square root of one mod 21.
And then, once we find this [inaudible]
square root, which is eight.
We looked at eight + one.
Take the GCD with 21.
The greatest common divisor.
We know how to do that quickly, using
Euclid's algorithm that you learned in
high school.
Once you do that, you'll find a nontrivial
square root of N and that's your factoring
algorithm.
Okay, so what does the, what does the
circuit finally look like for factoring?
This is what it looks like.
You start with two registers.
The first one, you start with value zero,
you perform a quantum theory transform
model.
This is the, this is the register, which
contain the answer value.
When you apply scenario, you put it
through this circuit for computing f which
is f(a) x^a mod N.
You, you either measure the answer or put
to, to f or remember you can always
discard it.
That's the same as measuring it.
Okay, so you discard it and now what you
are left with is this periodic
superposition on these first priors.
You put it through the contemporary
transform.
You measure even finding sub routine gives
you a way of reconstructing of what period
it is.
Once you know the period, you take x to
the period / two.
That's your nontrivial square root of one
mod N.
Okay.
Now you take that nontrivial square root +
one GCD with N, that should give you a
factor of N.
But remember it only works with
probability half.
So what do you do?
You take what, you know whatever this
algorithm on, outputs and check that it
divides N.
If it does, you have factorized N.
If not, try again because half the time it
works.
Okay, so that's it.
You, you now understand the factoring.