NPTEL

NATIONAL PROGRAMME ON
TECHNOLOGY ENHANCED LEARNING

IIT BOMBAY

CDEEP
IIT BOMBAY

Quantum Infromation and

Computing

Prof. [Link]
Department of Physics IIT Bombay

Modul No.05

Lecture No.27

Shor’s Factorization Algorithm

In the last lecture we had talked about the implementation of quantum Fourier transform. We
discussed in detail what happens to one, two and three qubit cases and then pointed out in
principle one could extend it to n qubits. These were components that we require for
implementing what is known as Shor’s factorizing algorithm. But before I go to Shor’s
factorization algorithm, let me point out a few things regarding the factorization and its status
with respect to classical algorithm.
(Refer Slide Time: 01:03)

So I am going to be concentrating on a situation in which I have a number 𝑁 = 𝑝𝑞 which is

product of two large primes 𝑝 and 𝑞, of course in this lecture, for the purpose of illustration I
will not be able to take 𝑝 and 𝑞 very large. I will necessarily take small values of 𝑝 and 𝑞 th
only to illustrate the principle. The power of quantum computation lies in the fact that the
algorithm that I will be discussing is applicable for large p and q. Now there are, in principle,
algorithms which can compute the factors of a large composite number or of a composite
number.

(Refer Slide Time: 01:53)

One of the algorithms is the Euclid algorithm. Basically it takes about √N steps and you can
see why, because if you are given a number of which there are two factors, except when it is
square of another number, one of the factors must be less than √𝑁 and the other factor more
than √𝑁. Thus one has to only obtain the factor which is less than √𝑁. Euclid algorithm is
not particularly suitable for large numbers and there are better algorithms much faster
algorithms in classical computing.
(Refer Slide Time: 02:37)

The fastest known algorithm in classical computation takes time of the order of
exp+(log 𝑁)1/3 (log log 𝑁)4/3 5. We will not go into how this expression is arrived at but it
shows that it is a time taking process and is slow. Though the factorization algorithm is slow,
the inverse process of multiplication of two numbers is fast and can be easily performed in
polynomial time.
(Refer Slide Time: 03:07)

Just to give you an idea of the problem involved, suppose I give you a not too large number,
say 29083. Finding its factors using pen and pencil is time consuming and may take a couple
of hours. Computers (even classical ones) will of course take less time but they also become
inefficient as the number becomes larger and larger.
(Refer Slide Time: 04:06)

However, if I tell you that this number is equal to 229 x 127 , back checking it is easy as it is
a simple multiplication. Thus multiplication is an easy problem but factorization is hard.
Before discussing Shor’s algorithm, let me tell you how this Euclid algorithm works. Euclid
algorithm works by determining greatest common divisor (GCD) of two numbers 𝑎 and 𝑏.
(Refer Slide Time: 04:32)

If the GCD is 𝑐, then both 𝑎 and 𝑏 may be expressed as multiples of c. Let 𝑎 = 𝑚𝑐 and 𝑏 =
𝑛𝑐, where 𝑚 and 𝑛 are integers. Notice one thing. Suppose 𝑏 < 𝑎. If I divide a by b, Now
notice one thing, that suppose I divide 𝑎 by 𝑏 , unless 𝑏 happens to be a factor of 𝑎, the
division will result in a remainder 𝑟.
(Refer Slide Time: 05:16)

Clearly, 𝑟 = 𝑎 − 𝑏𝑞, where 𝑞 is the quotient of the division. It can be seen that 𝑐 divides 𝑟
because 𝑟 = 𝑎 − 𝑏𝑞 = 𝑚𝑐 − 𝑛𝑐𝑞 = (𝑚 − 𝑛𝑞 )𝑐. What we do in Euclid algorithm is the
following. We start with a long division of You start with a long division of 𝑎 by 𝑏.
(Refer Slide Time: 06:08)

Let the quotient be 𝑞1 , so that the remainder is given by 𝑟1 = 𝑎 − 𝑏𝑞1 . Let me illustrate it by
taking 𝑎 = 75 and 𝑏 = 24. When I divide 𝑎 by 𝑏, I get quotient 𝑞1 = 3 and remainder 𝑟1 =
3. At this stage, I divide the divisor of the previous step, which was 24, by the remainder 𝑟1 ,
getting a quotient 𝑞4 and a remainder 𝑟4 . (In the given example, we divide 24 by 3 getting a
remainder 0). We continue this process, every time dividing the divisor of the previous stage
with the remainder obtained, till there is no remainder left. This remainder at the last stage is
the GCD 𝑐 that we set to determine., i.e. if the process gets completed at the n-th stage, we
DEFG
𝑐= DE
. This is the way Euclid's algorithm works. It is a decent algorithm which works well

for reasonably small numbers, but is no good if you take up very, very large numbers. So let
us look at how do we handle the situation here.
(Refer Slide Time: 08:31)

Recall the number 29803 which I had mentioned earlier. To find its factor, what you have to
do is try to find the GCD of this number and another number less than or equal to the square
root of this number. Starting with 3, check each odd number less than the square root of
29803 and find the GCD of the pair. Since there is no factor less than 127, in each case less
than 127, the GCD will work out to 1. This is the way Euclid algorithm is used for
factorization.
(Refer Slide Time: 08:40)

Shor suggested that instead you solve an equivalent problem, and this equivalent problem is
called period finding.
(Refer Slide Time: 08:59)

You might recollect that we have mentioned about finding periods and its connection with
the Fourier transform.
(Refer Slide Time: 09:10)

So what we will do is the first step in Shor's algorithm.

(Refer Slide Time: 09:18)

Given an N choose a random number m, which is less than N (𝑚 < 𝑁), which is coprime
with N. Let me explain what is meant by two numbers being co-prime. Two numbers are said
to be coprimes if they have no common factor among themselves. For instance 15 and 14 are
primes (though neither of them is a prime) because they do not have any common factor.
Whether two numbers are co-primes or not can be easily verified by Euclid type algorithm.
(Refer Slide Time: 10:28)

Having chosen such an m, we need to find its various powers mod N.

(Refer Slide Time: 10:46)

I define a function 𝑓I (𝑎) = 𝑚J mod N. Recall 𝑚 is that random number that I chose which
was coprime with N. We are doing discrete mathematics, i.e. the powers are evaluated and
reduced to their value modulo N. Let 𝑚K = 1 mod N, where P is the smallest value of the
power 𝑎 which satisfies this property. We call this process modular exponentiation. This
smallest value of P that we obtain is called period of the function that I have defined. I will
just give you a numerical example of how it works.
(Refer Slide Time: 12:06)
(Refer Slide Time: 12:10)

Let me take a small number for the purpose of illustration so that I can calculate its various
powers manually. Let N=21.
(Refer Slide Time: 12:29)

If we take N=21 of course you will say that I know it is 3x7, but then I am not going to be
using a quantum computer to find out the factors of 21,55 etc. But this is to illustrate the
principle behind it rather than actually doing a serious computation.
(Refer Slide Time: 12:50)

We choose m randomly. Let’s take it to be 2 which clearly has no common factor with 21 and
hence is co-prime with 21. Let us compute various powers of 2 mod 21. The are
21 = 1, 24 = 4, 23 = 8, 2N = 16, 2P = 32 = 11 𝑚𝑜𝑑 21.
(when a number exceeds N, you subtract enough multiples of N so that what you are left with
is less than N). We continue like this and next we have
2S = 64 = 63 + 1 = 21 × 3 + 1 = 1 𝑚𝑜𝑑 21
Thus 6 is the smallest integer P such that 2K = 1 𝑚𝑜𝑑 𝑁. Hence the period of the function 2
mod 21 is P=6.
(Refer Slide Time: 14:06)

The choice of m was random; excepting for the fact that it should be co-prime with 21, there
is no other restriction. For instance we could have taken m to be 4, 5, 8, 10, 11, 13, 16, 17, 19
or 20. The numbers left out are 3, 6, 7, 9, 12, 15 and 18 which have common factors with 21.

Now what is the relationship of this power calculation with factorization? Now in order to be
that I will need some elementary result from discrete algebra, I will not be proving all of
them but such proofs are available in any standard textbook but I will be only be illustrating
the principle. Consider a quadratic equation for instance.
(Refer Slide Time: 15:16)

x2 = 1 mod N. Now if N is a prime, I should more appropriately say, if N is an odd prime

then one can show that this equation has only trivial solutions that is x = + or – 1. On the
other hand, if N happens to be a composite number, then, in addition to the trivial solutions
there are also non-trivial solutions of the problem. Pair of non-trivial solutions, for instance x
could be some + or - a ,remember these are modular arithmetic so when I say something is +
or - a it means it is that quantity + k times number N. To illustrate what I mean by this
statement let us consider the following. Consider the solution

of x2 = 1 mod 41. this equation only has trivial solution and the reason is that 41 is a prime
number odd prime number but on the other hand consider 55. Then I claim that because 55 is
a composite number, the equation x2 = 1 mod 55 has, in addition to the trivial solution, has a
pair of non-trivial ones and these you can easily calculate. I claim that x equal to +or - 21 are
solutions. Now you can see why because if x = + or – 21, x2 = 441, which is = 1 mod 440
recall 440 is eight times 55 so therefore this is also = 1 mod 55. What is the connection of
this theorem with whatever we are doing. We have chosen mP = 1.
(Refer Slide Time: 18:16)

so that tells me that if I choose x = mP/2 then this equation gets converted to an x2 = 1
equation, mod N of course.
(Refer Slide Time: 18:45)

Now obviously in order that I can do that my P has to be even. So one of the requirements of
Shor’s algorithm is P better be even.
(Refer Slide Time: 19:04)

If P is odd, the algorithm fails and what we do in that case just go back choose the different m
and carry on again until you are successful. Now if P is even, I write this equation by
V V
factorizing (𝑚 W + 1 )(𝑚 W − 1 ) = 0 mod N. Now remember that this is discrete
mathematics so when something is 0 mod N it does not mean it is =0 per se. It simply means
it is 0 + 𝑘𝑁, where 𝑘 is an integer. However, the second factor cannot be 0 mod N because
of our definition of the period, that P is the smallest number that satisfies 𝑚K = 1.
(Refer Slide Time: 20:33)

Now the other possibility is mP/2 +1 is 0 mode N which means mP / 2 + 1 is some k times N.
now if that happens also the algorithm fails and we must return to the beginning and choose
a different 𝑚 and proceed once again.
(Refer Slide Time: 21:10)

However, if MP/2+1 is also not equal to 0 mos N, then I can proceed further. It has been
shown that the probability of these two things happening, i.e., (i) that the period for a
random number be even and (ii) given that it is even, MP/2+1 being not equal to 0 mod N
has reasonably high probability. For product of two prime numbers this can be shown to be
greater than half but I will not go through the probability calculations. But suppose these two
conditions are satisfied.
(Refer Slide Time: 22:12)

the only way we can satisfy this equation is that each of these terms contains a factor of N.
(Refer Slide Time: 22:52)
(Refer Slide Time: 22:53)

Now it is this order finding part that needs to be done by a quantum computer and the reason
is that if N is large then all powers of N will have to be calculated and that becomes a time
consuming task in a classical computer. But in the quantum computer all powers of m will
be simultaneously calculated. From this we still have to extract the value of P that meets our
requirement.
(Refer Slide Time: 23:41)

So this is the summary of what we have talked about so far. Now let me illustrate that how
this works.
(Refer Slide Time: 24:00)

I will illustrate the above by a couple of examples. First, consider N = 21. we have shown
that the period of this number for 𝑚 = 2 is 6. We then have P/2=1. Hence +𝑚K/4 +
15+𝑚K/4 − 15 = 0 mod N can be written as (23 + 1)(23 − 1) = 0 mod 21, which requires
9 × 7 = 0 mod 21. We can see that 9 contains one of the factors of 21, viz., 3 and 7 the other
factor.

As a second example let us take N = 35. In this case let me choose 𝑚 = 13, which is co-
prime to 35 because13, 35 have no common factors. Now check 134 = 169, 133 I do not
need to calculate because if it were 1 mod 35 then of course my algorithm will fail because
the exponent of 13 is odd. In this case it is not. 13N = 28561, which is 816 times 35. Thus P
= 4 in this case.
(Refer Slide Time: 25:53)
(Refer Slide Time: 26:02)

Since P = 4, I get (132 + 1) x (132 -1)=0 mod 35, which means these two factors contain the
factors of 35. You can check that the equation implies 170 x168=0 mod 35. 170 obviously
has one of the factors, i.e. 5 and the second one 168 can be found to have 7 as a factor. Now
that explains how this is carried out. Now what I have to do now is this to get these into
implementation, so let us quickly summarize what we have done today.

We have given an algorithm which is actually the most important part of the algorithm which
has to be done in a quantum computer and this requires calculation of a period of a discrete
function (we defined the discrete function as raising the power of a random number which is
co-prime to the given N) for which you want to find out the factors.

This random number, raised to certain power, should be equal to 1. So this step requires
calculation of various powers of this random number and that part can be done very
efficiently by a quantum computer. If this period of the function which is the minimum value
of the power for which mP = 1 mod N, then by a theorem of discrete algebra we find that it
has nontrivial solution when my N is a composite number.

And then we factorized this mP = 1 or rather mP – 1=0 as ( mP/2 + 1 )x (mP/2 – 1)=0 and we
showed that each one of these now contains a factor of the original number. What we are
going to do next is to find out or is to decide, discuss how does a computer quantum
computer actually implemented.

NATIONAL PROGRAMME ON TECHNOLOGY

ENHANCED LEARNING
(NPTEL)

NPTEL
Principal Investigator
IIT Bombay

Prof. R.K. Shevgaonkar

Head CDEEP

Prof. V.M. Gadre

Producer

Arun kalwankar

Online Editor
& Digital Video Editor

Tushar Deshpande

Digital Video Cameraman

& Graphic Designer

Amin B Shaikh

Jr. Technical Assistant

Vijay Kedare

Teaching Assistants

Pratik Sathe
Bhargav Sri Venkatesh M.

Sr. Web Designer

Bharati Sakpal

Research Assistant

Riya Surange

Sr. Web Designer

 Bharati M. Sarang

Web Designer

Nisha Thakur

Project Attendant

Ravi Paswan
Vinayak Raut

NATIONAL PROGRAMME ON TECHNOLOGY

ENHANCED LEARNING
(NPTEL)

Copyright NPTEL CDEEP IIT Bombay