What is Shor’s Algorithm?

Shor’s Algorithm is a quantum algorithm that can factor large integers efficiently by using quantum period-finding, which classical algorithms cannot do in polynomial time.

Why is Shor’s Algorithm important?

Because it threatens classical cryptographic schemes (like RSA) by allowing factorization of large numbers in feasible time on a sufficiently powerful quantum computer — demonstrating quantum advantage.

How does Shor’s Algorithm work in brief?

It uses quantum superposition and the quantum Fourier transform to find the period of a function related to the integer, then uses that period to compute non-trivial factors of the integer.

Does Shor’s Algorithm break all encryption today?

Not yet — practical quantum computers large enough to break widely used cryptosystems are still under development. But Shor’s Algorithm shows the potential risk.

Shor's Algorithm

Shor’s algorithm is one of the most famous quantum algorithms, created by mathematician Peter Shor in 1994. It showed, for the first time, that a quantum computer could solve a problem much faster than any known classical method.

The problem it solves is called integer factorization, breaking a large number $ N $ into the prime numbers that multiply to make it:

\[ N = p \times q \]

This is important because the security of many encryption systems, such as RSA, is based on the fact that factoring large numbers is slow on classical computers.

How Shor’s Algorithm Works

First, choose a random number $ a $ that is smaller than $ N $.
Then, using quantum computing, find the period $ r $ of the function $ f(x) = a^x \bmod N $. The period is the smallest number $ r $ such that: $$ a^r \equiv 1 \pmod{N} $$
Once $ r $ is known, it can be used to find the factors of $ N $ efficiently.

Finding the period r is where quantum computing shines. A classical computer would need to test many values of $ x $, but a quantum computer can find $ r $ quickly using a process called the Quantum Fourier Transform (QFT).

Once the period is known, the remaining steps are simple math done on a normal computer to find the factors.

Applications of Shor's Algorithm

Breaking Cryptography – Can factor large integers efficiently, threatening RSA, Diffie–Hellman, and elliptic curve cryptography.
Advances in Number Theory – Provides fast solutions for factorization and discrete logarithm problems, aiding research in mathematics.
Driving Post-Quantum Cryptography – Motivates the development of new encryption methods resistant to quantum attacks

Shor’s Algorithm Example – Factoring 15

Let’s understand how Shor’s Algorithm works using a simple example: finding the prime factors of N = 15.

Step 1: Choose a Random Number $ a $

Pick an integer such that $ 1 < a < N $. Let’s pick $ a = 2 $.

Step 2: Compute gcd(a, N)

$ \text{gcd}(2, 15) = 1 $ → no factor found, continue.

Step 3: Define the Function

$ f(x) = a^x \bmod N = 2^x \bmod 15 $

x	2^x	2^x mod 15
0	1	1
1	2	2
2	4	4
3	8	8
4	16	1

The pattern repeats every 4 steps.

Step 4: Find the Period $ r $

The period $ r $ is the smallest number such that $ a^r \equiv 1 \ (\text{mod } N) $. Here, $ 2^4 \equiv 1 \ (\text{mod } 15) $. So, $ r = 4 $.

Step 5: Quantum Period Finding

On a real quantum computer, the Quantum Fourier Transform (QFT) is used to find $ r $ efficiently. This is where the quantum speed-up happens — QFT finds the period exponentially faster than classical methods.

Step 6: Compute Factors

Once $ r = 4 $ is known:

$ a^{r/2} = 2^2 = 4 $

Compute the gcd values:

$ \text{gcd}(4 - 1, 15) = \text{gcd}(3, 15) = 3 $
$ \text{gcd}(4 + 1, 15) = \text{gcd}(5, 15) = 5 $

✅ The factors of 15 are 3 and 5.

In simple terms: Shor’s algorithm turns a hard factorization problem into an easy period-finding problem, and uses quantum waves to find that period almost instantly.

Quantum Computing