Polynomial-Time Algorithms for Prime
Factorization and Discrete Logarithms
on a Quantum Computer - Peter W. Shor
Presented by:
Abhijith Raju Nair (B22079)
Aadi Chandra Modak (B22283)
● RSA Algorithm
● RSA is one of the most widely used asymmetric key
cryptosystem.
● Based on the difficulty of factoring large prime numbers.
● It uses a pretty simple but effective algorithm for key generation.
○ Choose 2 large prime numbers p and q.
𝜙 = (p-1)*(q-1)
○ Compute public key N=p*q
○ Compute private key
● The public key is used to encrypt messages and private key is
used to decrypt messages.
RSA
● Now what this means is that if we can extract p and q from the
public key N, we can calculate the private key and decrypt the
messages ourselves.
● So all we have to do is calculate the prime factors of N and be on
our way, right?
But it’s not so simple!
● For large prime numbers, prime factorization is computationally
expensive. In fact, as the number increases, the time required to
factorize it increases exponentially making it practically infeasible
to crack the 2048 bit length keys that have become standard
nowadays.
Quantum Computers: What’s the
difference?
● Unlike classical computers, quantum computers can process
multiple states at once due to superposition, leading to
exponential speedup in certain types of problems.
● Quantum computers(QC) use quantum bits(qubits) as opposed to
classical bits which represent both 0 and 1 at the same time,
allowing them to explore many solutions simultaneously.
What are Quantum algorithms?
● Qubits are the fundamental building blocks of QCs, but how do
we run a program using these mysterious entities.
● The answer to that would be: Quantum Algorithms
● Quantum Algorithms are composed of many Quantum
Gates(more on that later) operating on these qubits, which
manipulate them similarly to how classical gates transform bits
to get an output that we desire.
● Now let us delve into the basic terminologies so as to get a better
understanding of how these work
Qubits
● A qubit is like a bit but instead of being in a single state(0
or 1) it is in a superposition of the basis states |0> and |
1>.
● A state of a qubit is the probabilities of each basis state as
well as a phase which we’ll discuss in the next slide.
● A qubit is represented on a Bloch sphere where |0> is at
the north pole and |1> is at the south pole.
● Every other point on the sphere represents a superposition
of both states. At the equator both states have an equal
probability of being measured
Qubits
Qubits
Typically a state |Q> of a qubit is represented as the combination |
0> and |1>. The combined state of multiple qubits is represented
by the tensor product.
Note: The squares of the constants should add
Quantum Gates
● Similarly to classical logic
gates, these gates perform
operations on a single qubit
or multiple qubits to
transform them.
Quantum Gates
Quantum Algorithms
● Quantum algorithms work by manipulating qubits through
quantum gates to exploit the unique properties of quantum
mechanics.
● The process begins with the initialization of qubits, often set to a
known state. These qubits are then transformed by a series of
quantum gates.
● For a wide range of algorithms, the state are initialized to an
equal superposition using Hadamard gates.
● The key to quantum algorithms is that they are designed to
maximize the probability of obtaining the correct result upon
Shor's Algorithm
Shor’s algorithm deals with prime factorization of integers and
achieves exponential speedup compared to classical algorithms.
This is a major deal as a lot of major cryptographic schemes such
as RSA and DH key exchange are based of the fact that
factorization of very large prime numbers takes a very long time.
It was one of the first quantum algorithms to show practical
applications.
It take as compared to
for classical algorithms.
It utilizes Quantum Phase Estimation which in turn applies Inverse
Quantum Fourier Transform (QFT)
Quantum Fourier Transform
effectively changes the basis of
the state from the computational
basis ( |0> and |1> ) to the
Fourier basis ( |0~> and |1~>).
In the case of a single qubit
system this can be simplified to
just a Hadamard (H) gate
QFT
The generalized form for QFT follows
that of a classical Fourier transform
And in terms of single qubits:
Where UROTk
applies phase
to |1> state.
Shor’s Algorithm
Now that we have explained QFT, we are at a point
where we can start explaining shor’s algorithm.
1. First we pick a number “a” that is coprime with N
and find the order of modular exponentiation with
a with modulus N. This is where we use our
quantum algorithm.
2. This stage is completely classical. We calculate
and find gcd(x+1,N) and gcd(x-1,N). There is a
high probability for p or q to be one of these or
both. From here it is trivial to
Step by Step Shor
Taking
a=13
When we measure, the state will collapse into either 0, 4, 8
or 12.
● r=0 gives us no information
● r=4 gives us
x=13^(4/2) mod 15 = 4
x+1=5, x-1=3 which are the factors of 15.
● r=8 gives
x=13^(8/2) mod 15 = 1
This does not give us our desired values
● r=12 gives
x=4
Which also gives us {5,3}
Thanks!