# Shor’s Algorithm (for Dummies)

--

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) = 6GCD (12, 48) = 12GCD (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 = 212 mod 41 = 1236 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 = 44 + 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

= 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) = 7f₂ = 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