Shor's Algorithm Explained | QuantumComputingCourses.com

Integer Factorization

Consider the number 15. Its prime factors are easily found: 3 × 5. Now, imagine a 2048-bit number, roughly 617 decimal digits long. Finding its prime factors is practically impossible using classical methods. The best known classical algorithm, the general number field sieve, requires roughly 2^100 operations. Even if every computer on Earth had been running since the Big Bang, factoring a 2048-bit number would remain out of reach. Shor’s algorithm changes this. It solves the problem in polynomial time, requiring only about O((log N)³) quantum operations. This exponential speedup makes Shor’s algorithm the most important quantum algorithm for cybersecurity.

How Factoring Breaks RSA

RSA encryption relies on a simple mathematical asymmetry: multiplying two large primes is easy, but factoring their product is hard.

To generate an RSA key, the process is straightforward:

Select two large primes: p = 61, q = 53 (in practice, these are about 1024 bits each).
Calculate N = p × q = 3233.
Publish N as part of the public key.

The security of RSA rests on the assumption that factoring N back into p and q is computationally infeasible. Classical computers cannot perform this task for large N. Quantum computers, however, running Shor’s algorithm can.

Factoring Reduces to Period Finding

Shor’s algorithm does not factor a number directly. Instead, it reduces the problem of factoring to period finding, a task that quantum computers can handle efficiently.

The reduction proceeds as follows:

Step 1: Pick a random integer a where 1 < a < N and gcd(a, N) = 1. (If gcd ≠ 1, you have accidentally found a factor, and the process is complete.)

Step 2: Find the period r of the function:


f(x) = aˣ mod N

Find the smallest $r$ such that $a^r \equiv 1 \pmod{N}$ .

Step 3. With high probability, at least one of these is a non-trivial factor.


gcd(a^(r/2) - 1, N)
gcd(a^(r/2) + 1, N)

Classical computers cannot find $r$ fast enough for large $N$ . The quantum part of Shor’s algorithm finds $r$ in polynomial time using the Quantum Fourier Transform (QFT).

The classical Discrete Fourier Transform (DFT) converts a sequence in the time domain to the frequency domain, revealing periodic patterns. The Fast Fourier Transform (FFT) performs this conversion using $O(N \log N)$ operations.

The Quantum Fourier Transform (QFT) acts on quantum states encoding amplitudes. It performs the equivalent transformation using only $O((\log N)^2)$ operations, which is exponentially faster. However, there is a limitation: measurement collapses the state, so you cannot read out all the amplitudes. What you can do is use interference to make the period $r$ appear with high probability when you measure.

Conceptually, the QFT circuit for $n$ qubits involves several steps. First, a Hadamard gate is applied to the first qubit. Next, controlled phase rotations of angle $\pi/2^k$ are applied to each subsequent qubit. This process is then repeated for every qubit. Finally, the qubit ordering must be reversed using SWAP gates.

# Qiskit: QFT on n qubits
from qiskit import QuantumCircuit
import numpy as np

def qft(n):
    qc = QuantumCircuit(n)
    for j in range(n):
        qc.h(j)
        for k in range(j+1, n):
            angle = np.pi / (2 ** (k - j))
            qc.cp(angle, k, j)  # controlled phase
    # Swap qubits to correct bit ordering
    for j in range(n // 2):
        qc.swap(j, n - j - 1)
    return qc

Full Shor’s Algorithm Structure


Classical preprocessing:
  1. Pick random a (1 < a < N)
  2. Check gcd(a, N) - if ≠ 1, we got lucky, done

Quantum period finding:
  3. Prepare |0⟩|0⟩ (input register + output register)
  4. Apply H⊗ⁿ to input register → uniform superposition
  5. Apply modular exponentiation: |x⟩|0⟩ → |x⟩|aˣ mod N⟩
  6. Measure output register (collapses input to states with same aˣ mod N)
  7. Apply Inverse QFT to input register
  8. Measure input register → get a multiple of N/r

Classical post-processing:
  9. Use continued fractions to extract r from measurement
  10. Compute gcd(a^(r/2) ± 1, N)
  11. Check if result is a non-trivial factor
  12. Repeat if r is odd or a^(r/2) ≡ -1 (mod N)

Modular Exponentiation

Implementing Shor’s algorithm faces its greatest challenge in step 5: modular exponentiation.

The goal is to compute $|x\rangle|0\rangle \rightarrow |x\rangle|a^x \bmod N\rangle$ for all $x$ in superposition simultaneously. This quantum circuit operation is the quantum equivalent of evaluating $f(x) = a^x \bmod N$ for every possible $x$ at once. To achieve this, we need an efficient reversible quantum circuit for modular multiplication, a task that is deeply non-trivial to implement on current hardware.

The circuit depth required for modular exponentiation scales as $O((\log N)^3)$ . This depth accounts for most of the quantum gates used in Shor’s algorithm, which explains why factoring cryptographically-relevant numbers requires millions of physical qubits (when considering error correction).

Factoring 15: A Small Example

Let’s trace Shor’s algorithm using $N = 15$ .

First, we perform classical preprocessing: we select $a = 7$ . Since $\gcd(7, 15) = 1$ , we can proceed.

Next, we tackle the quantum period finding step: we must find $r$ for the function $f(x) = 7^x \bmod 15$ .

7¹ mod 15 = 7
7² mod 15 = 4
7³ mod 15 = 13
7⁴ mod 15 = 1   ← period r = 4

Classical post-processing: The value of r is 4, which is even. We calculate $7^{(4/2)}$ , yielding $7^2 = 49$ . Next, we determine the greatest common divisor for two cases. First, $\text{gcd}(49 - 1, 15) = \text{gcd}(48, 15)$ , which equals 3. Second, $\text{gcd}(49 + 1, 15) = \text{gcd}(50, 15)$ , which equals 5. Finally, we confirm the factorization of 15: $15 = 3 \times 5$ .

# Simplified Shor's for N=15 using Qiskit
# (The full circuit is complex; this shows the structure)
from qiskit import QuantumCircuit
from qiskit_aer import AerSimulator
from qiskit import transpile
import math

def shors_classical_part(N, a, r):
    """Given period r, attempt to extract factors."""
    if r % 2 != 0:
        return None  # Try different a
    x = pow(a, r // 2, N)
    if x == N - 1:
        return None  # Try different a
    factor1 = math.gcd(x - 1, N)
    factor2 = math.gcd(x + 1, N)
    if factor1 not in (1, N):
        return factor1
    if factor2 not in (1, N):
        return factor2
    return None

# For N=15, a=7: r=4 (found by quantum part)
result = shors_classical_part(15, 7, 4)
print(f"Factor found: {result}")  # 3 or 5

Resource Requirements for Real Cryptographic Attacks

To break RSA-2048 using Shor’s algorithm, the resource requirements are substantial. Estimates show that approximately 4,000 logical qubits are needed, which translates to about 4,000,000 physical qubits when accounting for error correction. The process requires around $10^{10}$ gate operations and, if run on a future quantum computer, would take hours to days.

Current quantum computers face significant limitations. IBM and Google have systems in the 100-1,000 physical qubit range with improving fidelity, and Google demonstrated below-threshold error correction with surface codes in 2023. However, scaling to millions of error-corrected physical qubits has not been demonstrated. The gap between today’s technology and the ability to break RSA-2048 is measured in decades, not years.

However, this threat is not immediate. The development of post-quantum cryptography standards (NIST FIPS 203, 204, 205) was finalized in 2024 specifically to prepare for this challenge.

Post-Quantum Cryptography Response

NIST standardized three algorithms in 2024: FIPS 203, which uses ML-KEM (formerly CRYSTALS-Kyber) based on module lattices; FIPS 204, which uses ML-DSA (formerly CRYSTALS-Dilithium) also based on module lattices; and FIPS 205, which uses SLH-DSA (formerly SPHINCS+) based on hash functions.

These algorithms are believed to resist both classical and quantum attacks, including those from Shor’s algorithm. This security stems from the fact that they rely on mathematical problems that Quantum Fourier Transform (QFT) does not help solve.

Shor’s Algorithm versus Grover’s Algorithm

These two algorithms represent different types of quantum speedup. Shor’s algorithm provides exponential speedup, applying to problems like factoring and discrete logarithms. Its cryptographic impact is severe, as it breaks RSA, ECC, and DH. Conversely, Grover’s algorithm provides only a quadratic speedup, applicable to unstructured search problems, which effectively halves the security level of symmetric keys. While Shor’s algorithm is not compatible with current Noisy Intermediate-Scale Quantum (NISQ) devices because it is too deep, Grover’s algorithm can be partially implemented for small search spaces. Neither algorithm is practically useful today.

Summary

Shor’s algorithm remains the prime example of exponential quantum advantage. The process begins with the problem of factoring large integers, a task that is classically intractable at cryptographic scales. The quantum solution reduces factoring to period finding, then uses QFT to find that period exponentially faster. Since RSA, ECC, and Diffie-Hellman all rely on the difficulty of factoring or discrete logarithms, understanding Shor’s algorithm is essential for assessing the long-term security implications of quantum computing. The current response involves deploying post-quantum cryptography standards, such as ML-KEM and ML-DSA. However, the timeline for a quantum computer capable of breaking current encryption remains years to decades away, requiring millions of error-corrected physical qubits.