1
00:00:00,000 --> 00:00:05,007
Okay, but, but now remember N is a very
large number.

2
00:00:05,007 --> 00:00:09,001
Right?
It's a 1000 digit number.

3
00:00:09,001 --> 00:00:14,008
We are still looking for a needle in a
haystack, because we are looking for this

4
00:00:14,008 --> 00:00:20,001
non-trivial square root of one mod n.
There are only two of them, two out of

5
00:00:20,001 --> 00:00:24,008
these ten to the 1000 numbers.
What chance we have of finding them?

6
00:00:24,008 --> 00:00:28,005
So this is where we use another kind of
approach.

7
00:00:28,005 --> 00:00:33,008
So let's again do this by example, and
then we'll see the general principle.

8
00:00:33,008 --> 00:00:43,049
So let's pick a number mod, mod, mod 21.
So let's say we pick a number like two.

9
00:00:43,049 --> 00:00:52,001
And, now we look at, we look at the powers
of two, okay?

10
00:00:52,001 --> 00:00:57,018
So, let's look at two^0 = one.
Two^1 = two.

11
00:00:57,018 --> 00:00:59,082
Two^2 =
Four.

12
00:00:59,082 --> 00:01:07,056
Again, looking at everything mod 21,
right?

13
00:01:07,056 --> 00:01:11,002
There is always mod the number we are
trying to factor.

14
00:01:14,000 --> 00:01:22,076
>> How about two cubed?
It's eight mod 21.

15
00:01:22,076 --> 00:01:34,006
Two^4 = sixteen mod 21.
Two^5, Well it's 32 but what's 32?

16
00:01:34,006 --> 00:01:44,003
It's, 32 is eleven mod 21. two^6 is,
eleven two = 22.

17
00:01:44,003 --> 00:01:47,002
What's 22?
It's one mod 21.

18
00:01:47,002 --> 00:01:52,063
Okay.
So now is it significant that two^6 = one

19
00:01:52,063 --> 00:01:58,008
mod 21?
Well, yes it is because what this tells

20
00:01:58,008 --> 00:02:04,005
us, since two^6 is congruent to one mod
21.

21
00:02:04,005 --> 00:02:13,068
What this tells us is that if we take two
cubed and we square it, this is two^6

22
00:02:13,068 --> 00:02:20,017
which is one mod 21, so this means that
two cubed.

23
00:02:20,017 --> 00:02:26,004
This is a nontrivial square root of one
mod 21, right?

24
00:02:26,004 --> 00:02:29,003
But what's two cubed?
That's eight.

25
00:02:29,003 --> 00:02:33,006
Remember?
That was the number that we found which

26
00:02:33,006 --> 00:02:38,001
was a nontrivial square root of, of, of
one mod 21.

27
00:02:38,001 --> 00:02:42,006
So we have found eight squared is
congruent to one mod 21.

28
00:02:43,000 --> 00:02:46,000
Okay.
So now, what's the general principle

29
00:02:46,000 --> 00:02:50,065
underlying in all this?
So this, here's the general lemma which I

30
00:02:50,065 --> 00:02:56,053
won't prove but if you, if you wish to
understand how to prove it you can, you

31
00:02:56,053 --> 00:03:01,074
can look up the reference that I gave.
So, what it says is, that this happens in

32
00:03:01,074 --> 00:03:05,057
complete generality.
So let N be an odd composite.

33
00:03:05,057 --> 00:03:12,001
Now N And, and let's say that N has at
least two distinct prime, prime factors.

34
00:03:12,001 --> 00:03:17,004
You know, that's the case that we are
interested in because now we, we want to

35
00:03:17,004 --> 00:03:21,003
factorize N.
And it says, suppose we pick x uniformly

36
00:03:21,003 --> 00:03:27,005
random between zero and N - one.
And which is relatively prime to N.

37
00:03:27,005 --> 00:03:32,011
Because if it's not relative, so we pick
an x uniformly random between zero and N -

38
00:03:32,011 --> 00:03:35,002
one.
If GCD of x and N is not equal to one,

39
00:03:35,002 --> 00:03:39,001
then we're already done because we have
managed to factorize it.

40
00:03:39,001 --> 00:03:45,002
So, but if GCD of x and N is one which is
the usual case, then with probability at

41
00:03:45,002 --> 00:03:49,049
least a half.
The order x mod N is even and x^r/2 is a

42
00:03:49,049 --> 00:03:54,092
non trivial square root of one whatever.
What do you mean by this?

43
00:03:54,092 --> 00:03:59,082
So what it means, what we mean by this is,
it can accept random mod N.

44
00:03:59,082 --> 00:04:09,004
So this was like picking two mod 21.
And now you find the minimum non-zero

45
00:04:09,004 --> 00:04:18,008
minimum positive power of x mod N.
So find what power you must raise it to so

46
00:04:18,008 --> 00:04:24,001
that you get one.
Okay.

47
00:04:24,006 --> 00:04:31,000
So this r is called the order.
Of x mod N.

48
00:04:31,000 --> 00:04:41,022
So now, what this lemma is telling us is,
if he picks, picks x at random, then half

49
00:04:41,022 --> 00:04:53,037
the time we've been the good case where r
is even and x^R/2 is not congruent to + or

50
00:04:53,037 --> 00:04:59,026
-one mod N.
So if you call this x^r/2y, then we have

51
00:04:59,026 --> 00:05:08,007
the case that y is not congruent to + or
-one mod N but y squared, which is x^r is

52
00:05:08,007 --> 00:05:14,003
congruent to one mod N.
So we found our nontrivial square root of

53
00:05:14,003 --> 00:05:19,001
one mod N and we can use it to factor, as
we saw before.

54
00:05:19,001 --> 00:05:22,005
Okay.
But, this still leaves us with a problem.

55
00:05:22,005 --> 00:05:27,007
How do we actually compute this?
You know, we, we, we, we found, you know

56
00:05:27,007 --> 00:05:32,004
we pick an x at random.
It's going to work with probability half,

57
00:05:32,004 --> 00:05:36,000
that's great.
But how do we find this order of x?

58
00:05:36,000 --> 00:05:39,002
Because order of x can be very, very
large.

59
00:05:39,002 --> 00:05:43,004
It can be you know comparable in size to
N.

60
00:05:43,004 --> 00:05:48,002
But N, remember, is a thousand bit,
thousand digit number.

61
00:05:48,002 --> 00:05:53,005
So, so N is like ten to the 1000.
So, the order might be this huge number

62
00:05:53,005 --> 00:05:57,002
and we can't, we can't be raising x to
every power.

63
00:05:57,002 --> 00:06:04,069
So, what's the short cut?
Okay so, so let's go back and let's, let's

64
00:06:04,069 --> 00:06:11,006
look at what we do.
So, so let's make up a, a, you know so

65
00:06:11,006 --> 00:06:21,009
we've picked this number, number x = two.
We are working, we have N = 21.

66
00:06:21,009 --> 00:06:26,073
And now let's, let's just build up a
table.

67
00:06:26,073 --> 00:06:40,003
So, so let's, Let's build a, build a table
where, where we have a number A and here

68
00:06:40,003 --> 00:06:44,001
we have x^a mod N.
Okay.

69
00:06:44,001 --> 00:06:52,065
So think of, think of this as f of a.
Okay, so when we have a = zero, what's,

70
00:06:52,065 --> 00:06:55,091
what's x to the zero mod, mod 21?
It's one.

71
00:06:55,091 --> 00:06:58,028
A
= one.

72
00:06:58,028 --> 00:07:05,039
What's two^1 mod, mod 21?
It's two.

73
00:07:05,039 --> 00:07:15,087
Equal to two and four, three, eight, four,
sixteen.

74
00:07:15,087 --> 00:07:20,040
Five.
Okay, what's two to the five?

75
00:07:20,040 --> 00:07:23,069
It's 32.
32 mod 21 = eleven.

76
00:07:23,069 --> 00:07:37,003
Six, one remember that was the order two
mod 21. seven now we start repeating.

77
00:07:37,003 --> 00:07:46,075
Two, eight, four, nine, eight ten,
sixteen, eleven.

78
00:07:46,075 --> 00:07:54,059
Sixteen^32, we get back to eleven.
Twelve, we're back to one.

79
00:07:54,059 --> 00:08:02,054
Thirteen, two, fourteen, four.
Okay you see the pattern right?

80
00:08:02,054 --> 00:08:06,038
You get this periodic function.
Okay.

81
00:08:06,038 --> 00:08:10,067
What are we trying to find?
We are trying to find the order.

82
00:08:10,067 --> 00:08:14,045
What's the order?
Well, it's a period of this periodic

83
00:08:14,045 --> 00:08:16,083
function.
So what should we do?

84
00:08:16,083 --> 00:08:21,048
Well, so here's a function that we can
compute efficiently.

85
00:08:21,048 --> 00:08:26,060
What we should do is period finding,
right?

86
00:08:26,060 --> 00:08:32,044
So what do we do in period finding?
We set up a superposition.

87
00:08:32,044 --> 00:08:40,004
We go into a sum over all a.
And if you, if you do this over a range of

88
00:08:40,004 --> 00:08:45,004
M, 1/ square root M.
A = zero^M-1.

89
00:08:45,004 --> 00:08:52,003
And then, we are in, we are in this
superposition over a, of a, f(a) and then

90
00:08:52,003 --> 00:08:58,097
we measure this register.
What happens when we measure this

91
00:08:58,097 --> 00:09:03,001
register?
Let's say we get the value four.

92
00:09:03,002 --> 00:09:07,002
So we measure this register and we get the
value four.

93
00:09:07,002 --> 00:09:11,000
Now what's the, what's our first register
look like?

94
00:09:11,000 --> 00:09:16,089
Well, it's in a superposition over this.
Over everything where the second register'

95
00:09:16,089 --> 00:09:18,000
is four.
So that, ...

96
00:09:18,001 --> 00:09:22,002
>> That.
So now we get this periodic superposition.

97
00:09:22,002 --> 00:09:26,005
We have superposition over two, eight,
fourteen, right?

98
00:09:26,005 --> 00:09:32,002
It's periodic with period form.
And now when we do a fourier transform

99
00:09:32,002 --> 00:09:38,000
again, it shows up the period, right?
Once we have the period, we find a

100
00:09:38,000 --> 00:09:43,005
nontrivial square root of one mod 21.
And then, once we find this [inaudible]

101
00:09:43,005 --> 00:09:47,000
square root, which is eight.
We looked at eight + one.

102
00:09:47,000 --> 00:09:50,001
Take the GCD with 21.
The greatest common divisor.

103
00:09:50,001 --> 00:09:54,041
We know how to do that quickly, using
Euclid's algorithm that you learned in

104
00:09:54,041 --> 00:09:58,005
high school.
Once you do that, you'll find a nontrivial

105
00:09:58,005 --> 00:10:02,001
square root of N and that's your factoring
algorithm.

106
00:10:02,001 --> 00:10:07,001
Okay, so what does the, what does the
circuit finally look like for factoring?

107
00:10:07,001 --> 00:10:11,000
This is what it looks like.
You start with two registers.

108
00:10:11,000 --> 00:10:16,001
The first one, you start with value zero,
you perform a quantum theory transform

109
00:10:16,001 --> 00:10:20,008
model.
This is the, this is the register, which

110
00:10:20,008 --> 00:10:25,009
contain the answer value.
When you apply scenario, you put it

111
00:10:25,009 --> 00:10:32,000
through this circuit for computing f which
is f(a) x^a mod N.

112
00:10:32,003 --> 00:10:37,047
You, you either measure the answer or put
to, to f or remember you can always

113
00:10:37,047 --> 00:10:41,001
discard it.
That's the same as measuring it.

114
00:10:41,001 --> 00:10:46,004
Okay, so you discard it and now what you
are left with is this periodic

115
00:10:46,004 --> 00:10:51,039
superposition on these first priors.
You put it through the contemporary

116
00:10:51,039 --> 00:10:54,099
transform.
You measure even finding sub routine gives

117
00:10:54,099 --> 00:10:58,008
you a way of reconstructing of what period
it is.

118
00:10:58,008 --> 00:11:04,004
Once you know the period, you take x to
the period / two.

119
00:11:04,004 --> 00:11:09,001
That's your nontrivial square root of one
mod N.

120
00:11:09,007 --> 00:11:13,006
Okay.
Now you take that nontrivial square root +

121
00:11:13,006 --> 00:11:16,009
one GCD with N, that should give you a
factor of N.

122
00:11:16,009 --> 00:11:20,004
But remember it only works with
probability half.

123
00:11:20,004 --> 00:11:24,003
So what do you do?
You take what, you know whatever this

124
00:11:24,003 --> 00:11:27,008
algorithm on, outputs and check that it
divides N.

125
00:11:27,008 --> 00:11:33,001
If it does, you have factorized N.
If not, try again because half the time it

126
00:11:33,001 --> 00:11:34,008
works.
Okay, so that's it.

127
00:11:34,008 --> 00:11:38,003
You, you now understand the factoring.