Shor’s Algorithm (for Dummies)

6 min readOct 23, 2020

Factoring large numbers has always been a challenge for mathematicians. It is easy to multiply two numbers and get the product. But splitting the product into its factors is tedious. Even with more powerful and fast computers, the problem of factoring large integers is still not resolved.

However in 1994, American mathematician Peter Shor devised an Algorithm for Quantum computers that could be a breakthrough in factoring large integers.
Shor’s Factoring Algorithm is one of the best algorithms for factorization. The reason why it is so popular is the fact that given enough advancements in quantum computation, this algorithm can be used to break encryption. We will talk more about this later.

Table of Content

Some Math Terminologies
Getting Started
The Shor’s Algorithm
Quantum World & Encryption
Caveats

Some Math Terminologies

You’ll need to know some basic Math. I have given a brief description of some math terminologies that you will need in the process. If you already have a math background, you can skip this part.

GCD (or HCF)

Greatest Common Divisor (GCD) is the largest number that can divide any two given numbers. It is also called HCF or Highest Common Factor.
Eg.
GCD (18, 24) = 6
GCD (12, 48) = 12
GCD (15, 22) = 1
There are various ways to calculate GCD, the best being Euclid’s Division Algorithm.

Modulo Operator

It returns the remainder of a division.
Eg.
17 mod 5 = 2
12 mod 41 = 12
36 mod 9 = 0

Getting Started

You should note that not all numbers can be factorized by Shor’s Algorithm.

The number should :

Not be a prime number (obviously)
Not be an even number (coz then 2 will be a factor)
Not be of form nˣ (n^x)

The Shor’s Algorithm

This is a Step-By-Step explanation of the whole process with an example

Step 1

Let the number to be factorized be N. Make sure it fulfills all conditions.
Eg- Let’s factorize 15. So N=15.

Step 2

Choose randomly a number between 1 and N. Call this number 'k’.
Eg- We have to choose a number between 1 and 15. Let’s take 7. So, k=7.

Step 3

Find GCD (N, k). You could calculate it using Euclid’s Division Algorithm. If GCD is not equal to one, then congratulations! The GCD is a factor of N, so we are done.
If, however, GCD = 1, then proceed to Step 4.
Eg- GCD (15, 7) = 1
So, we move on to the next step.

Step 4

We need to find smallest positive integer r such that if
f(x) = kˣ mod N, then f(a) = f(a+r)
But don’t get overwhelmed by the mathness of the above statement, just follow the following steps to find r:

Step 4.1

Define a new variable q = 1.

Step 4.2

Find (q×k) mod N.
If the remainder is 1, proceed to Step 4.3. If not, set the value of 'q' to the value of the remainder we got. Repeat this step till you get remainder = 1 and keep track of how many times you did the transformation. Remember to change the value of 'q' every time.
Eg-

We did the transformation 4 times.

Step 4.3

The number of transformations you did in Step 4.2 is your value of r.
Eg- We did Step 4.2 four times. So, r = 4

Step 5

If r is odd, go back to Step 2 and choose a different value of k.
Eg- r = 4 is even, so we move on.

Step 6

Define p = remainder in (r/2)th transformation.
If p + 1 = N, then go back to Step 2 and choose a different value of k.
If not, proceed to Step 7.
Eg-
p will be the remainder in (4/2)th, i.e., 2nd transformation.
p = 4
4 + 1 = 5 is not equal to 15
So we can proceed.

Step 7

This is the final step. The factors of N are
f₁ = GCD (p+1, N)
f₂ = GCD (p-1, N)
Eg-
f₁ = GCD (p+1, N)
= GCD (5, 15)
= 5
f₂ = GCD (p-1, N)
= GCD (3, 15)
= 3
Therefore, 3 and 5 are factors of 15.

Example:

(chosen such that it covers all possible situations)

Let’s factorize N = 357
We randomly pick k = 205
GCD (357, 205) = 1

Therefore, r = 3
r is odd. So, we need to choose another value of k.
We randomly pick k = 152
GCD (357, 152) = 1

Therefore, r = 6
r is even. So, we can move on.
p will be the remainder in (6/2)th, i.e., 3rd transformation.
p = 356
Now we check if p + 1 = N
356 + 1 is equal to 357
So, we need to choose another value of k.
We randomly pick k = 52.
GCD (357, 52) = 1

Therefore, r = 6
r is even. So, we can move on.
p will be the remainder in (6/2)th, i.e., 3rd transformation.
p = 307
Now we check if p + 1 = N.
307 + 1 is not equal to 357.
So, now we can do the final step.
f₁ = GCD (308, 357) = 7
f₂ = GCD (306, 357) = 51
Therefore, 7 and 51 are factors of 357.

The Quantum World & Encryption

The Shor’s Algorithm is designed to run on a Quantum Computer and not on a classical computer as we did. On a Quantum Computer, the algorithm works waaa....aaay faster. Why?

Steps 1, 2, 3, 5, 6, and 7 can be done quite efficiently on a classical computer. But when it comes to Step 4, i.e., finding the value of subroutine r, classical computers fall short. This step takes the most amount of time in the whole algorithm. But Quantum Computers are an edge above! You can read more about How Quantum Computers Calculate Subroutine here. But before you begin to read it, I would like you to appreciate the efficiency of Quantum Computation.
Below is a rough time vs number graph comparing classical and quantum computation. It shows the amount of time required to factor in a number.

So for large integers, quantum computation is more suitable.

This may seem like a breakthrough (which it is) in computation and mathematics, but poses a possible threat to encryption. How?

Well, RSA - one of the most used schemes in encryption, depends on the assumption that factoring large numbers is practically impossible. If however, we could factor them, RSA would be broken. Research on encryption schemes that are quantum-proof had already begun to come up with alternatives to RSA. This led to the birth of something called post-quantum cryptography!

But no need to worry about your online security. Quantum Computation is still in its infancy. It would take at least a decade or two to build a practical, stable, Quantum Computer with sufficient memory to actually try to break encryption.

We have a lot of time…, don’t we?

Caveats

On a classical computer, Shor’s Algorithm is NOT the fastest algorithm to factor large integers. Other algorithms like General Number Field Sieve, Quadratic Sieve, and Lenstra Elliptic Curve factorization are much faster and suited for classical computation.
The Shor’s Algorithm works incredibly fast on quantum computers, but to date, the largest number factorized by a Quantum Computer using the Shor’s Algorithm is just 21. Other methods were able to achieve much higher on a Quantum Computer.

Explore more

“The Euclidean Algorithm” by Brett Berry
“How Quantum Computers Break Encryption” by minutephysics
“Shor, I’ll do it” by Scott Aaronson
“Encryption and HUGE numbers” by Numberphile
“Integer Factorisation Records” on Wikipedia
“Chinese Remainder Theorem” by Astarte Kraus