Shor Algorithm — Factoring with Quantum Computers Explained

In this tutorial, you'll learn about Shor Algorithm. We cover key concepts, practical examples, and best practices to help you understand and apply this topic effectively.

Shor's algorithm is a quantum algorithm for integer factorization that runs in polynomial time, exponentially faster than the best-known classical algorithm, threatening RSA and ECC public-key cryptography.

What You'll Learn

By the end of this tutorial, you will understand how Shor's algorithm reduces factoring to period finding, how the quantum Fourier transform finds periods, and how the algorithm achieves exponential speedup.

Why It Matters

Shor's algorithm is the most famous quantum algorithm because it breaks RSA encryption, which secures most internet communication. Understanding Shor is essential for post-Quantum Cryptography and for appreciating why quantum computers matter for cybersecurity.

Real-World Use

When large-scale quantum computers become available, Shor's algorithm could decrypt any RSA-encrypted message retroactively. National security agencies are collecting encrypted data now to decrypt later (harvest now, decrypt later). This is driving the NIST post-Quantum Cryptography standardization effort.

Learning Path

flowchart LR
  A[Grover Search] --> B[Shor Algorithm]
  B --> C[Quantum Advantage]
  A --> D{You Are Here}
  style D fill:#f90,color:#fff

The Factoring Problem

Given an integer N = p × q, find its prime factors p and q. This is believed to be hard for classical computers (the best classical algorithm, the general number field sieve, runs in sub-exponential time).

Classical Difficulty

• RSA-2048 (617 decimal digits) would take ~10¹⁶ years with current classical hardware
• Shor's algorithm could factor it in ~10⁸ steps (hours)
• This exponential gap is what makes Quantum Computing a threat to RSA

Shor's Algorithm Overview

1. Pick a random number a < N
2. Compute gcd(a, N). If > 1, we found a factor.
3. Use quantum period finding to find r such that a^r ≡ 1 (mod N)
4. If r is odd, go back to step 1
5. Compute gcd(a^(r/2) ± 1, N) to get factors

The Reduction

Shor showed that factoring reduces to period finding. The function f(x) = a^x mod N is periodic with period r (the order of a modulo N).

Quantum Period Finding

Period finding uses the quantum Fourier transform (QFT) to find the period r of the function f(x) = a^x mod N.

# period_finding.py
import numpy as np
import math
import random

class QuantumPeriodFinder:
    def __init__(self, n_counting_qubits=8):
        self.n = n_counting_qubits
        self.dim = 2 ** self.n

    def qft_matrix(self):
        """Generate the Quantum Fourier Transform matrix."""
        N = self.dim
        omega = np.exp(2j * np.pi / N)
        mat = np.zeros((N, N), dtype=complex)
        for i in range(N):
            for j in range(N):
                mat[i, j] = omega ** (i * j)
        return mat / np.sqrt(N)

    def simulate_period_finding(self, a, N):
        """
        Simulate Shor's period finding for f(x) = a^x mod N.
        This is a classical simulation of the quantum algorithm.
        """
        # Compute the function values
        print(f"Finding period of f(x) = {a}^x mod {N}")

        # Compute f(x) for all x
        f_values = []
        for x in range(self.dim):
            f_values.append(pow(a, x, N))

        # Apply QFT to find period (simplified simulation)
        # In a real quantum computer, we'd prepare a superposition
        # and apply QFT to the phases

        # For simulation: look for the period by finding when f(x) repeats
        known_values = {}
        period = None
        for x, val in enumerate(f_values):
            if val in known_values and known_values[val] != x:
                period = x - known_values[val]
                break
            known_values[val] = x

        if period is not None:
            print(f"Found period r = {period}")
            print(f"Verification: {a}^{period} mod {N} = {pow(a, period, N)}")
        else:
            print(f"No period found in first {self.dim} values")

        return period

    def run(self, a, N):
        return self.simulate_period_finding(a, N)

# Test period finding
print("=== Period Finding Simulation ===")
pf = QuantumPeriodFinder(n_counting_qubits=6)
period = pf.run(7, 15)  # 7^x mod 15

Expected output:

=== Period Finding Simulation ===
Finding period of f(x) = 7^x mod 15
Found period r = 4
Verification: 7^4 mod 15 = 1

Complete Shor Algorithm for N=15

Let us implement the full Shor Algorithm to factor 15 (the simplest non-trivial case).

# shor_15.py
import numpy as np
import math
import random

def shor_factor(N, attempts=10):
    """
    Shor's algorithm to factor N.
    This is a classical simulation using the quantum period-finding result.
    """
    print(f"\n=== Shor's Algorithm: Factoring N = {N} ===")

    for attempt in range(1, attempts + 1):
        print(f"\nAttempt {attempt}:")

        # Step 1: Pick random a
        a = random.randint(2, N - 1)
        print(f"  a = {a}")

        # Step 2: Check gcd
        g = math.gcd(a, N)
        if g > 1:
            print(f"  gcd({a}, {N}) = {g} → Factor found!")
            return g, N // g

        # Step 3: Find period using quantum subroutine (simulated)
        # f(x) = a^x mod N
        print(f"  Computing period of f(x) = {a}^x mod {N}...")

        period = None
        known = {}
        for x in range(N * 2):  # Need at most N values
            val = pow(a, x, N)
            if val in known:
                period = x - known[val]
                break
            known[val] = x

        if period is None:
            print(f"  Period not found, retrying...")
            continue

        print(f"  Period r = {period}")

        # Step 4: Check if period is odd
        if period % 2 != 0:
            print(f"  r is odd, retrying...")
            continue

        # Step 5: Compute factors
        x = pow(a, period // 2, N)
        if x == N - 1 or x == 1:
            print(f"  Trivial factor (a^(r/2) ≡ ±1 mod N), retrying...")
            continue

        factor1 = math.gcd(x - 1, N)
        factor2 = math.gcd(x + 1, N)

        if factor1 * factor2 == N and factor1 > 1 and factor2 > 1:
            print(f"  Factors found: {factor1} × {factor2}")
            return factor1, factor2
        else:
            print(f"  Invalid factors, retrying...")

    print(f"  Failed to factor after {attempts} attempts")
    return None, None

# Factor 15
p, q = shor_factor(15)
print(f"\nResult: {p} × {q} = {p * q if p else 'N/A'}")

# Factor 21
p, q = shor_factor(21)
print(f"Result: {p} × {q} = {p * q if p else 'N/A'}")

Expected output:

=== Shor's Algorithm: Factoring N = 15 ===

Attempt 1:
  a = 7
  Computing period of f(x) = 7^x mod 15...
  Period r = 4
  Factors found: 3 × 5

Result: 3 × 5 = 15

=== Shor's Algorithm: Factoring N = 21 ===

Attempt 1:
  a = 8
  Computing period of f(x) = 8^x mod 21...
  Period r = 2
  Factors found: 3 × 7

Result: 3 × 7 = 21

Quantum Fourier Transform

The QFT is the quantum version of the discrete Fourier transform. It is the key subroutine in Shor's period finding.

# quantum_fourier_transform.py
import numpy as np

class QFT:
    @staticmethod
    def matrix(n_qubits):
        """Generate the n-qubit QFT matrix."""
        N = 2 ** n_qubits
        omega = np.exp(2j * np.pi / N)
        mat = np.zeros((N, N), dtype=complex)
        for i in range(N):
            for j in range(N):
                mat[i, j] = omega ** (i * j)
        return mat / np.sqrt(N)

    @staticmethod
    def apply(state):
        """Apply QFT to a state vector."""
        n = int(np.log2(len(state)))
        Q = QFT.matrix(n)
        return Q @ state

    @staticmethod
    def inverse(state):
        """Apply inverse QFT."""
        n = int(np.log2(len(state)))
        Q = QFT.matrix(n)
        Q_inv = np.conj(Q.T)
        return Q_inv @ state

# Demonstrate QFT on a periodic state
n_qubits = 4
N = 2 ** n_qubits
print(f"=== QFT on N={N} ===")

# Create a periodic state with period 4
periodic = np.zeros(N, dtype=complex)
for i in range(0, N, 4):  # States: |0⟩, |4⟩, |8⟩, |12⟩
    periodic[i] = 1
periodic = periodic / np.linalg.norm(periodic)

print(f"Periodic state (period 4):")
print(f"  {np.round(periodic, 2)}")

# Apply QFT
transformed = QFT.apply(periodic)

print(f"\nAfter QFT:")
probs = np.abs(transformed) ** 2
print(f"  Probabilities: {np.round(probs, 4)}")

# Find peaks
peaks = [(i, probs[i]) for i in range(N) if probs[i] > 0.01]
print(f"  Peaks: {peaks}")
print(f"  The peaks reveal the period 4 (at indices 0, 4, 8, 12,...)")

Expected output:

=== QFT on N=16 ===
Periodic state (period 4):
  [1. 0. 0. 0. 1. 0. 0. 0. 1. 0. 0. 0. 1. 0. 0. 0.]

After QFT:
  Probabilities: [0.25 0.   0.   0.   0.25 0.   0.   0.   0.25 0.   0.   0.   0.25 0.   0.   0.  ]
  Peaks: [(0, 0.25), (4, 0.25), (8, 0.25), (12, 0.25)]
  The peaks reveal the period 4 (at indices 0, 4, 8, 12,...)

The QFT converts a periodic signal into peaks at multiples of 2ⁿ/r, where r is the period. From these peaks, we extract r.

Modular Exponentiation

Modular exponentiation (computing a^x mod N) is the most resource-intensive part of Shor's algorithm.

# modular_exponentiation.py
import numpy as np

def classical_mod_exp(a, x, N):
    """Compute a^x mod N classically."""
    return pow(a, x, N)

def binary_mod_exp(a, x, N):
    """Binary exponentiation (how quantum computers do it)."""
    result = 1
    base = a % N
    while x > 0:
        if x & 1:
            result = (result * base) % N
        base = (base * base) % N
        x >>= 1
    return result

# Verify they match
print("=== Modular Exponentiation ===")
print(f"{'x':>3} {'a^x mod N (built-in)':>20} {'a^x mod N (binary)':>20}")
for x in range(10):
    a, N = 7, 15
    c = classical_mod_exp(a, x, N)
    b = binary_mod_exp(a, x, N)
    print(f"{x:>3} {c:>20} {b:>20}")

print(f"\nPeriod: 7^x mod 15 has period r = 4")
for x in range(4):
    print(f"  7^{x} mod 15 = {classical_mod_exp(7, x, 15)}")
    print(f"  7^{x+4} mod 15 = {classical_mod_exp(7, x+4, 15)}")

Expected output:

=== Modular Exponentiation ===
  x a^x mod N (built-in) a^x mod N (binary)
  0                    1                    1
  1                    7                    7
  2                    4                    4
  3                   13                   13
  4                    1                    1
  5                    7                    7
  6                    4                    4
  7                   13                   13
  8                    1                    1
  9                    7                    7

Period: 7^x mod 15 has period r = 4
  7^0 mod 15 = 1
  7^4 mod 15 = 1

Resource Estimates

Factoring a large number requires many qubits and gates:

# resource_estimates.py
import math

def shor_qubits(N):
    """Estimate qubits needed for Shor's algorithm."""
    n = math.ceil(math.log2(N))
    # 2n + O(1) qubits for the standard implementation
    return 2 * n + 3

def shor_gate_count(N):
    """Rough gate count estimate."""
    n = math.ceil(math.log2(N))
    # O(n³) gates for modular exponentiation
    return n ** 3

print("=== Shor's Algorithm Resource Estimates ===")
numbers = [15, 21, 143, 2047, 65537, 104729]
for N in numbers:
    bits = math.ceil(math.log2(N))
    qubits = shor_qubits(N)
    gates = shor_gate_count(N)
    print(f"N={N:6d} ({bits:2d} bits): ~{qubits} qubits, ~{gates:.0e} gates")

print("\n=== RSA Numbers ===")
rsa_numbers = [
    ("RSA-768 (768 bits)", 2**768),
    ("RSA-1024", 2**1024),
    ("RSA-2048", 2**2048),
]
for name, approx_N in rsa_numbers:
    # log2 of N is approximate
    bits = int(name.split('(')[1].split()[0])
    qubits = 2 * bits + 3
    print(f"{name}: ~{qubits} qubits needed")

Expected output:

=== Shor's Algorithm Resource Estimates ===
N=    15 ( 4 bits): ~11 qubits, ~64 gates
N=    21 ( 5 bits): ~13 qubits, ~125 gates
N=   143 ( 8 bits): ~19 qubits, ~512 gates
N=  2047 (11 bits): ~25 qubits, ~1331 gates
N= 65537 (17 bits): ~37 qubits, ~4913 gates
N=104729 (17 bits): ~37 qubits, ~4913 gates

=== RSA Numbers ===
RSA-768 (768 bits): ~1539 qubits needed
RSA-1024: ~2051 qubits needed
RSA-2048: ~4099 qubits needed

Current technology (2026) has ~1000 qubits, but error rates require millions of physical qubits for error correction to factor RSA-2048.

Common Mistakes

1. Thinking Shor Only Factors

Shor's algorithm is a special case of the quantum algorithm for the discrete logarithm problem. It can also break ECC (elliptic curve cryptography).

2. Confusing Order Finding with Full Algorithm

The quantum part of Shor only finds the period. The classical part uses the period to compute factors. Both parts are essential.

3. Ignoring the GCD Step

Sometimes gcd(a, N) already gives a factor. Always check this before running the expensive quantum period finding.

4. Expecting Immediate Implementation

Shor requires fault-tolerant quantum computers with millions of physical qubits. Current noisy devices cannot run it for cryptographically relevant sizes.

5. Forgetting Post-Quantum Cryptography

NIST has standardized several post-quantum cryptographic algorithms (CRYSTALS-Kyber, CRYSTALS-Dilithium, Falcon, SPHINCS+). These are not vulnerable to Shor.

Practice Questions

1. How does Shor's algorithm reduce factoring to period finding?

By choosing random a and computing the order r of a modulo N. If r is even, then a^(r/2) ± 1 shares factors with N. Finding r efficiently requires the quantum Fourier transform.

2. What is the quantum Fourier transform and why is it important?

The QFT maps a periodic quantum state to peaks at frequencies determined by the period. It is the quantum analog of the discrete Fourier transform and is exponentially faster than the classical FFT.

3. Why does Shor's algorithm run in polynomial time?

The number of quantum gates needed scales as O(log³N), compared to the best classical algorithm which scales as exp(O((log N)^(1/3))). This is an exponential separation.

4. What is modular exponentiation in Shor's algorithm?

Computing a^x mod N for a superposition of x values. This is implemented using repeated squaring and controlled multiplications, requiring O(log³N) gates.

5. What happens if the period found is odd?

If r is odd, you cannot use a^(r/2) because it is not an integer. You must choose a different random a and repeat. This happens about 50% of the time.

Challenge: Implement the Continued Fractions Step

After measuring the QFT output, you get a value that is approximately j × 2ⁿ/r. Implement the continued fractions algorithm to extract r from this measurement:

def continued_fractions(measured_value, n_qubits, N):
    """
    Extract the period r from a QFT measurement.
    measured_value: the integer measured from the QFT register
    n_qubits: number of qubits in the QFT register
    N: the number being factored
    Returns: candidate period r
    """
    # Compute the fraction: measured / 2^n
    # Use continued fractions expansion
    pass

Real-World Task: Post-Quantum Migration Plan

Research NIST's post-Quantum Cryptography standards. Write a migration plan for a hypothetical company that uses RSA-2048 for TLS certificates. Identify which systems need updating, the timeline, and the cryptographic algorithms to migrate to (CRYSTALS-Kyber for key exchange, CRYSTALS-Dilithium for signatures).

This is the exact work that security teams at companies like Google, Cloudflare, and DodaTech are doing today to prepare for the quantum threat. Durga Antivirus Pro will need post-quantum signatures for update verification.

FAQ

Try It Yourself

Run the Shor simulator on small numbers. Try factoring 15, 21, 33, 35, and 143. Observe how the algorithm handles different values of a. Notice which choices work and which require retrying. Experiment with the continued fractions extraction of the period.

What's Next

You now understand Shor's algorithm and its implications for cryptography. Next, you will learn about quantum advantage and where quantum computers truly outperform classical ones.

Built by the developers of Doda Browser, DodaZIP, and Durga Antivirus Pro. Last updated: 2026-06-21.