1
00:00:00,000 --> 00:00:02,086
Okay.
So now, in this lecture, you'll finally

2
00:00:02,086 --> 00:00:06,066
understand Shore's Algorithm for factoring
integers.

3
00:00:06,066 --> 00:00:12,096
So, and remember, what we did in the last
lecture, we talked about this primitive

4
00:00:12,096 --> 00:00:17,032
called period finding.
And so today, we'll see how to use this,

5
00:00:17,032 --> 00:00:20,007
this primitive in order to factor
integers.

6
00:00:20,007 --> 00:00:27,002
So, remember, what period finding does,
it, you are given a function f from some

7
00:00:27,002 --> 00:00:32,030
domain, like the integers from zero to N -
one.

8
00:00:32,030 --> 00:00:39,000
It's a function from that, from, from
integers mod N to, to just some set.

9
00:00:39,000 --> 00:00:45,004
And this function has a property that it's
periodic with period r.

10
00:00:45,004 --> 00:00:50,000
Let f(x) = f (x) + r.
Your challenge is to find r.

11
00:00:50,000 --> 00:00:54,019
So, we saw that this is a difficult task
to do classically.

12
00:00:54,019 --> 00:01:00,049
But under that, quantumly you can do this
very efficiently and the way you do this

13
00:01:00,049 --> 00:01:05,045
is you have a circuit which looks very
much like the one we saw for Simon's

14
00:01:05,045 --> 00:01:14,018
algorithm so you have a Quantum Fourier
transform modem followed by the circuit of

15
00:01:14,018 --> 00:01:17,007
computer.
Followed by another Quantum Fourier

16
00:01:17,007 --> 00:01:22,040
transform modem and then you measure and
this, the result of this measurement gives

17
00:01:22,040 --> 00:01:25,054
you allows you to reconstruct what r is,
okay?

18
00:01:25,054 --> 00:01:31,057
So, again, remember, remember how we, how
we said in the case of Simon's algorithm,

19
00:01:31,057 --> 00:01:37,005
the quantum circuit could be seen as, as,
as a virtual two slit, double slit

20
00:01:37,005 --> 00:01:40,095
experiment.
So, in the case of period finding, the

21
00:01:40,095 --> 00:01:47,018
circuit can be seen as a virtual multiple
slit experiment, because after you do this

22
00:01:47,018 --> 00:01:52,089
Quantum Fourier transform you're in a,
superposition over all the numbers a mod

23
00:01:52,089 --> 00:01:57,042
N.
And then, then when you compute U, or

24
00:01:57,042 --> 00:02:07,069
compute f, you get summation over a of e
modem, followed by f(e) modem, right?

25
00:02:07,069 --> 00:02:18,089
So, this was sum over all a from zero to N
-one of a, a out here and zero out here

26
00:02:18,089 --> 00:02:27,061
and then after you do the compute f,
you'll get sum over all a equal to zero to

27
00:02:27,061 --> 00:02:38,000
N - one and this contains a and this
contains f(a).

28
00:02:38,009 --> 00:02:45,009
And so, now, when you, when you measure
this, you will see some value of, you

29
00:02:45,009 --> 00:02:52,034
know, f, f(a) and then, in the first
register you have a superposition over a,

30
00:02:52,034 --> 00:02:56,092
a + r, a + 2r, and so on.
So, these are you multiple slits that

31
00:02:56,092 --> 00:03:02,011
you've carved virtual slits.
And then, when you do a Quantum Fourier

32
00:03:02,011 --> 00:03:08,013
transform, you get interference button
which, which tells you, you know, because,

33
00:03:08,013 --> 00:03:13,089
because these slits are r apart, you get
interference at some quantity related to

34
00:03:13,089 --> 00:03:16,043
r.
And so, using that, you can reconstruct

35
00:03:16,043 --> 00:03:21,031
what r was, the period was.
Okay, so now, how do we use this to factor

36
00:03:21,031 --> 00:03:24,079
a number?
So, remember what the factoring problem

37
00:03:24,079 --> 00:03:28,088
is.
You're given some number N and you want to

38
00:03:28,088 --> 00:03:37,008
write it in the form in its prime factors,
p1 to the e1, p2 to the e2, pk to the ek.

39
00:03:37,008 --> 00:03:46,022
Right now, if N is a, you know, if' N was
a thousand digit number, then classically,

40
00:03:46,022 --> 00:03:52,019
this is very hard to factor.
Of course, the most naive algorithm would

41
00:03:52,019 --> 00:03:56,076
just try all prime factors until you,
until you find one.

42
00:03:56,076 --> 00:04:03,036
But then, if N were, in the hard cases
where N was a product of two primes, P

43
00:04:03,036 --> 00:04:09,004
times Q and say that each of P and Q is a
500 digit prime number.

44
00:04:09,004 --> 00:04:14,007
So now, in this case, trial division is
going to take way too long.

45
00:04:14,007 --> 00:04:21,035
It'll take ten to the, the, ten^500
possible factors, divisors to try and

46
00:04:21,035 --> 00:04:26,041
that's just, that's just hopeless.
Now, the fastest algorithms we know

47
00:04:26,041 --> 00:04:31,038
classically are much better than this.
But this still take exponential time.

48
00:04:31,038 --> 00:04:36,042
And so, this is why the factoring problem
is considered cryptographically hard.

49
00:04:36,042 --> 00:04:39,047
And that's the basis of the RSA cryptic
system.

50
00:04:39,047 --> 00:04:42,049
Okay.
So, for the purposes of this lecture, just

51
00:04:42,049 --> 00:04:49,004
to make things conceptually simple, I'm
going to assume N is of this form, it's of

52
00:04:49,004 --> 00:04:53,005
the form P times Q, where P and Q are two
odd primes.

53
00:04:53,005 --> 00:04:59,004
But, but, of course, everything I say is
going to be completely general and so

54
00:04:59,004 --> 00:05:05,002
it'll, it's going to work for any N, you
know, any compositor, which is, let's,

55
00:05:05,002 --> 00:05:07,046
let's say, any odd compositor.
Okay.

56
00:05:07,046 --> 00:05:13,067
So, generally, more, more generally, if,
if the number of digits or the number of

57
00:05:13,067 --> 00:05:17,059
bits, the length of number is little n,
right?

58
00:05:17,059 --> 00:05:25,011
Then, if, if little n is the number of,
number of bits that it takes to write out

59
00:05:25,011 --> 00:05:30,069
capital N, then capital N is about, two to
the little n.

60
00:05:30,069 --> 00:05:39,050
And a classical algorithm, the best
classical algorithms take time which is

61
00:05:39,050 --> 00:05:51,003
exponential in square root of N, okay?
By contrast, a quantum algorithm for, for

62
00:05:51,003 --> 00:06:01,042
computing, for finding the, the factors of
N is going to run, so this is, this is,

63
00:06:01,042 --> 00:06:10,019
this is best classical algorithm and by
contrast, a quantum algorithm for

64
00:06:10,019 --> 00:06:17,075
computing, for finding these, the prime
factorization of, of N, we'll run in time

65
00:06:17,075 --> 00:06:25,057
which is polynomial, say, order N^3
Although we can, we can improve it, the,

66
00:06:25,057 --> 00:06:31,002
the, the exponent might be squared or
using certain tricks we can improve it

67
00:06:31,002 --> 00:06:34,063
even further.
But, but, the most important thing here is

68
00:06:34,063 --> 00:06:38,022
that it goes from exponential time to
polynomial time.

69
00:06:38,022 --> 00:06:43,043
So now, in order to understand how this
algorithm works, we are going to have to

70
00:06:43,043 --> 00:06:48,073
understand some, you know, we're, we're
going to have to understand some very

71
00:06:48,073 --> 00:06:53,008
elementary number theory, theoretic facts,
which I'll now explain to you.

72
00:06:53,008 --> 00:06:57,079
But to, to understand these, these, these
simple facts, you, you'll, of course, need

73
00:06:57,079 --> 00:07:04,008
some background in what's called Modular
Arithmetic.

74
00:07:05,001 --> 00:07:08,007
I, I hope you already have this
background.

75
00:07:08,007 --> 00:07:14,034
If not, let me point you to the, to the,
to some resources online that will, that

76
00:07:14,034 --> 00:07:19,060
will, help you understand that.
So, what's meant by Modular Arithmetic?

77
00:07:19,060 --> 00:07:25,088
We say that two numbers, A and B are
congruent mod N, if A - B is divisible by

78
00:07:25,088 --> 00:07:29,007
N.
So, think of Modular Arithmetic as what

79
00:07:29,007 --> 00:07:33,083
happens when you, when you have numbers
around a clock face.

80
00:07:33,083 --> 00:07:39,030
So, they are counting modular twelve.
So, for example, if, if the time is

81
00:07:39,030 --> 00:07:44,056
fifteen o'clock, well, you don't ever
think of fifteen o'clock, you subtract off

82
00:07:44,056 --> 00:07:50,033
twelve and you get a number always between
zero and, well, okay, so if you're, if

83
00:07:50,033 --> 00:07:56,085
you're really doing it mod twelve then you
don't, you know, you call twelve, zero so

84
00:07:56,085 --> 00:08:02,001
you, your, your numbers are always zero,
one, two, three up to eleven, okay?

85
00:08:02,001 --> 00:08:08,028
Now if you don't already know about
Modular Arithmetic, let me refer to you

86
00:08:08,028 --> 00:08:13,055
some, an online resource.
There's a book on algorithms that you

87
00:08:13,055 --> 00:08:19,013
know, I've posted on my webpage.
This is, you know, this is the, an almost

88
00:08:19,013 --> 00:08:22,072
final copy.
This was a pre-copy edited version of the

89
00:08:22,072 --> 00:08:25,078
book.
And the first chapter is, you know, is on

90
00:08:25,078 --> 00:08:30,050
Modular Arithmetic.
The second half of the second chapter is

91
00:08:30,050 --> 00:08:35,055
on the Fast Fourier transform.
And chapter ten is on quantum factoring

92
00:08:35,055 --> 00:08:40,087
so, so, you have this, you know, you have
this resource available if you, if you

93
00:08:40,087 --> 00:08:46,048
need to look up any of the background for,
for Modular Arithmetic or some of these

94
00:08:46,048 --> 00:08:48,036
later, later topics.
Okay.

95
00:08:48,036 --> 00:08:53,057
So, so now, assuming everybody knows about
Modular Arithmetic, let's, let's just go

96
00:08:53,057 --> 00:08:58,076
ahead and say, let's, let's work with an
example, let's say that let's say that we

97
00:08:58,076 --> 00:09:03,007
have N = 21.
This is the number that we are trying to

98
00:09:03,007 --> 00:09:09,007
factor and we are pretending that N is
very large, 21 is too large for us to deal

99
00:09:09,007 --> 00:09:14,001
with by any of our standard methods.
So, what are we going to do?

100
00:09:14,001 --> 00:09:21,094
Well, it turns out that okay so, so
normally, if you, if you were looking at

101
00:09:22,026 --> 00:09:32,090
the square root of one you know, in
regular arithmetic, this would be plus or

102
00:09:32,090 --> 00:09:37,028
minus one.
And, of course, indeed, that's, that's

103
00:09:37,028 --> 00:09:42,088
also through mod N.
So, for example, you have one^2 is

104
00:09:42,088 --> 00:09:49,081
congruent to one mod 21.
And -one, which is also twenty when you,

105
00:09:49,081 --> 00:10:00,000
when you square it, you'll also get, one
mod 21, okay?

106
00:10:00,000 --> 00:10:06,000
So, so, you know, -one is the same thing
as twenty mod 21 and if you, if you go

107
00:10:06,000 --> 00:10:14,034
ahead and square twenty, you will get 400
and, and you should check that 400 is

108
00:10:14,034 --> 00:10:20,002
congruent to one mod 21.
Of course, you don't need to do this

109
00:10:20,002 --> 00:10:26,005
because, you know twenty is-1 but, okay.
Now, it turns out that mod N, when N is a

110
00:10:26,005 --> 00:10:33,001
composite, these are not the only two
numbers that square to one mod N.

111
00:10:33,001 --> 00:10:37,003
So, there is another square root of, of,
of 21.

112
00:10:37,009 --> 00:10:47,051
And that happens to be eight, because
eight^2, which is 64, I can see when you,

113
00:10:47,051 --> 00:10:55,000
you use mod 21, 21 times three is 63 and
so, the reminder is one.

114
00:10:55,000 --> 00:11:03,035
So, eight^2 is 64, which is one mod 21,
okay?

115
00:11:03,035 --> 00:11:09,072
So, I claim that once you locate such a
nontrivial, we, we call this a nontrivial

116
00:11:09,072 --> 00:11:15,054
square root of one mod 21.
Once you have such a, such a nontrivial

117
00:11:15,054 --> 00:11:22,081
square root, you can use it to factor 21
because, because now, what we can claim is

118
00:11:22,081 --> 00:11:29,088
the G, the GCD eight + one and 21, the
greatest common divisor is, is going to

119
00:11:29,088 --> 00:11:37,062
give you a nontrivial square root and the
GCD of eight - one and 21 will also give

120
00:11:37,062 --> 00:11:42,007
you a nontrivial square root of,
nontrivial factor of 21.

121
00:11:42,007 --> 00:11:47,022
Okay.
So, what's the greatest common divisor of

122
00:11:47,022 --> 00:11:54,007
eight + one which is nine and 21?
Well, the greatest common divisor of these

123
00:11:54,007 --> 00:12:00,008
two numbers is, is three, which is indeed
one of the factors of 21.

124
00:12:00,008 --> 00:12:07,040
And this number is, the seven, and the GCD
of seven and 21 is, is seven, so, so we

125
00:12:07,040 --> 00:12:15,020
manage to find, we manage to factorize 21
just by computing this nontrivial square

126
00:12:15,020 --> 00:12:19,087
root of one mod 21.
Now, of course, there's another, there

127
00:12:19,087 --> 00:12:27,011
should be another nontrivial square root
because they come in, they come in pairs,

128
00:12:27,011 --> 00:12:34,007
and that would be -eight.
-Eight is, is the same as, what's -eight

129
00:12:34,008 --> 00:12:44,003
mod 21?
It's, it's -eight + 21, which is thirteen.

130
00:12:44,004 --> 00:12:49,094
So, I claim -eight^2 which is thirteen^2
is also common to one mod 21.

131
00:12:49,094 --> 00:12:58,007
That's a 169 and you should, you should
check that 168 is, is divisible by 21.

132
00:12:58,007 --> 00:13:04,008
And so, you could have done the same thing
with thirteen.

133
00:13:04,008 --> 00:13:12,070
You could have said, GCD of thirteen plus
one and 21 is going to be nontrivial.

134
00:13:12,070 --> 00:13:21,000
So, this was14, and indeed the GCD is, the
greatest divisor is seven.

135
00:13:21,000 --> 00:13:29,014
Also, the GCD of thirteen - one and 21.
Well, what's this?

136
00:13:29,014 --> 00:13:36,008
This is twelve, the GCD is three, okay,
so, you recover the factors of N, okay.

137
00:13:36,008 --> 00:13:42,009
So, so, what's going on here?
Well, what's going on here is this general

138
00:13:42,009 --> 00:13:47,003
principle.
If x is a nontrivial square root of one

139
00:13:47,003 --> 00:13:54,024
mod N, ten the GCD of x + one and N, N is
the GCD of x - one and N give you

140
00:13:54,024 --> 00:13:59,041
nontrivial factors of N.
How do you prove this?

141
00:13:59,041 --> 00:14:05,006
Well, let's see.
X is a nontrivial square root of one mod

142
00:14:05,006 --> 00:14:11,010
N, meaning x is not congruent to plus or
minus one mod N.

143
00:14:11,010 --> 00:14:20,006
But it's the square root of one mod N, so
meaning, x^2 is congruent to one mode N.

144
00:14:21,003 --> 00:14:29,085
What's another way of saying this?
Meaning, x^2 - one is congruent to zero

145
00:14:29,085 --> 00:14:37,092
mod N, which means that N divides x^2 -
one.

146
00:14:37,093 --> 00:14:45,091
Okay, but then N divides (x + one) (x -
one).

147
00:14:45,091 --> 00:14:55,062
Okay, but, but what do we with this?
Well, remember also, x is not congruent to

148
00:14:55,062 --> 00:15:01,043
plus or minus one mod N, which is the same
thing assigned by the same kind of

149
00:15:01,043 --> 00:15:06,094
reasoning that N does not divide.
X plus or minus one.

150
00:15:06,094 --> 00:15:16,030
Okay, so, so now, N divides x + one times
x - one, but N does not divide x + one and

151
00:15:16,030 --> 00:15:20,026
N does not divide x - one.
So, how could it be?

152
00:15:20,026 --> 00:15:25,051
How could it be that N divides this
product but it doesn't divide either one?

153
00:15:25,051 --> 00:15:30,035
Okay.
Well, only way it could be is if some of

154
00:15:30,035 --> 00:15:35,041
the prime factors of N divide x - one and
some of them divide x - one.

155
00:15:35,041 --> 00:15:40,075
So now, what this tells us is that the
greatest common divisor of x + one and N

156
00:15:40,075 --> 00:15:46,020
must, must be a part of N, but [unknown]
is saying, it's just a product of two

157
00:15:46,020 --> 00:15:50,002
primes.
So, this must be the smallest of the prime

158
00:15:50,002 --> 00:15:54,004
factors.
And the greatest common divisor of x-1 and

159
00:15:54,004 --> 00:15:57,063
N must be less than other prime factor,
alright?

160
00:15:57,063 --> 00:16:02,044
So, for example, this might give us P,
this might give us Q, and that's how we

161
00:16:02,044 --> 00:16:03,005
can factor.