Shor’s Factoring Algorithm

Shor’s Factoring Algorithm#

Polynomial-time integer factorization using quantum period-finding. Why this threatens RSA and the motivation for post-quantum cryptography.

Shor’s algorithm (1994) is the most consequential quantum algorithm discovered to date. It factors integers in polynomial time, breaking the computational hardness assumption that underpins RSA, DSA, ECDH, and ECDSA. This single algorithm is the reason post-quantum cryptography exists.

The Problem#

Integer Factorization: Given a composite integer \(N\), find a non-trivial factor \(p\) such that \(1 < p < N\) and \(p | N\).

The best known classical algorithm (General Number Field Sieve) runs in sub-exponential time: \(O(\exp(c \cdot (\ln N)^{1/3} (\ln \ln N)^{2/3}))\). Shor’s algorithm runs in polynomial time: \(O(n^3)\) where \(n = \log N\) is the number of bits.

Algorithm	Time Complexity	Type
Trial division	\(O(\sqrt{N})\)	Classical
Pollard’s rho	\(O(N^{1/4})\)	Classical (heuristic)
GNFS	\(O(\exp(1.9 \cdot n^{1/3} (\ln n)^{2/3}))\)	Classical
Shor’s	\(O(n^3)\)	Quantum

The Reduction: Factoring to Period-Finding#

Shor’s key insight is that factoring reduces to finding the period of a function. The reduction is classical:

Pick a random \(a < N\) with \(\gcd(a, N) = 1\)
Find the order \(r\) of \(a\) modulo \(N\): the smallest positive integer such that \(a^r \equiv 1 \pmod{N}\)
If \(r\) is even and \(a^{r/2} \not\equiv -1 \pmod{N}\), then \(\gcd(a^{r/2} \pm 1, N)\) gives a non-trivial factor

Step 2 is the hard part classically. Quantum computers solve it efficiently using the Quantum Fourier Transform.

Why Period-Finding Works

The function \(f(x) = a^x \bmod N\) is periodic with period \(r\) (the order of \(a\)). If \(r\) is even, then \(a^r - 1 = (a^{r/2} - 1)(a^{r/2} + 1) \equiv 0 \pmod{N}\). Since \(a^{r/2} \not\equiv \pm 1\), neither factor is divisible by \(N\), so \(\gcd(a^{r/2} - 1, N)\) and \(\gcd(a^{r/2} + 1, N)\) are non-trivial factors. The probability that a random \(a\) yields a useful \(r\) is at least \(1/2\).

The Quantum Part: Period-Finding#

The quantum subroutine estimates \(r\) using two registers:

First register: \(n\) qubits for the input (initialized in uniform superposition)
Second register: \(n\) qubits for the output (stores \(a^x \bmod N\))

The steps:

Prepare \(\frac{1}{\sqrt{2^n}} \sum_{x=0}^{2^n - 1} |x\rangle |0\rangle\)
Compute \(f\): \(\frac{1}{\sqrt{2^n}} \sum_x |x\rangle |a^x \bmod N\rangle\)
Apply QFT to the first register
Measure the first register to obtain an estimate of \(j/r\) for some integer \(j\)
Use the continued fractions algorithm to extract \(r\) from \(j/r\)

The QFT converts the periodic structure in the amplitudes into sharp peaks at multiples of \(2^n/r\), enabling efficient extraction of the period.

Resource Estimates#

For factoring an \(n\)-bit number:

Resource	Estimate
Qubits	\(2n + O(\log n)\) (textbook), \(\sim 2n\) (optimized)
Gates	\(O(n^3)\) with schoolbook multiplication, \(O(n^2 \log n)\) with FFT-based
Circuit depth	\(O(n^3)\)

For RSA-2048 (\(n = 2048\)):

Logical qubits needed: ~4,000
Physical qubits (with surface codes at \(10^{-3}\) error rate): ~20 million
Runtime estimate: hours to days (depending on clock speed and code distance)

Important

No quantum computer has factored a cryptographically relevant number. The largest number factored by Shor’s algorithm on real hardware is 21 (using 5 qubits, heavily optimized). The gap between current hardware and what is needed for RSA-2048 is enormous, but the algorithm’s existence motivates the ongoing transition to post-quantum cryptography.

Threat to Cryptography#

Shor’s algorithm (and its extension to discrete logarithms) breaks:

Cryptosystem	Problem	Status
RSA	Integer factorization	Broken by Shor
DSA	Discrete logarithm	Broken by Shor
ECDH / ECDSA	Elliptic curve discrete log	Broken by Shor
Diffie-Hellman	Discrete logarithm	Broken by Shor
AES-256	Symmetric key search	Grover reduces to \(2^{128}\) (still secure)
SHA-256	Hash preimage	Grover reduces to \(2^{128}\) (still secure)

This is why NIST standardized post-quantum cryptographic algorithms (ML-KEM, ML-DSA, SLH-DSA) based on problems believed to be hard for quantum computers.

Implementations#

Qiskit

from qiskit import QuantumCircuit
from qiskit.circuit.library import QFT
import math

def shor_period_finding(a, N, n_count):
    """Quantum period-finding circuit for a^x mod N."""
    qc = QuantumCircuit(n_count + N.bit_length(), n_count)

    # Initialize counting register in superposition
    qc.h(range(n_count))

    # Initialize work register to |1>
    qc.x(n_count)

    # Controlled modular exponentiation
    for i in range(n_count):
        power = pow(a, 2**i, N)
        # Simplified: apply controlled multiplication by power mod N
        # Full implementation requires modular arithmetic circuits
        pass  # Placeholder for c-U^(2^i)

    # Inverse QFT on counting register
    qc.append(QFT(n_count, inverse=True), range(n_count))

    qc.measure(range(n_count), range(n_count))
    return qc

# Example: factor 15, a=7
# Full implementation requires modular exponentiation circuits
# See Qiskit textbook for complete worked example

Cirq

import cirq
import fractions

def make_order_finding_circuit(a, N, n_count):
    """Construct the QPE-based order finding circuit."""
    qubits = cirq.LineQubit.range(n_count + N.bit_length())
    count_qubits = qubits[:n_count]
    work_qubits = qubits[n_count:]

    circuit = cirq.Circuit()

    # Superposition on counting register
    circuit.append(cirq.H.on_each(*count_qubits))

    # |1> in work register
    circuit.append(cirq.X(work_qubits[0]))

    # Controlled modular exponentiation
    # (implementation depends on specific N and a)

    # Inverse QFT
    circuit.append(cirq.qft(*count_qubits, inverse=True))

    circuit.append(cirq.measure(*count_qubits, key='phase'))
    return circuit

# Extract period from measured phase using continued fractions
def extract_period(measured_phase, n_count, N):
    phase = measured_phase / (2**n_count)
    frac = fractions.Fraction(phase).limit_denominator(N)
    return frac.denominator

PennyLane

import pennylane as qml
import numpy as np

def shor_subroutine(a, N, n_count):
    """
    Shor's period-finding subroutine.
    Note: Full modular exponentiation requires
    problem-specific circuit construction.
    """
    n_work = int(np.ceil(np.log2(N)))
    dev = qml.device("default.qubit", wires=n_count + n_work)

    @qml.qnode(dev)
    def circuit():
        # Counting register in superposition
        for i in range(n_count):
            qml.Hadamard(wires=i)

        # Work register initialized to |1>
        qml.PauliX(wires=n_count)

        # Controlled modular exponentiation
        # ... (problem-specific implementation)

        # Inverse QFT on counting register
        qml.adjoint(qml.QFT)(wires=range(n_count))

        return qml.probs(wires=range(n_count))

    return circuit

PyQuil

from pyquil import Program
from pyquil.gates import H, X, MEASURE
from pyquil.quilbase import Declare

def shor_circuit(a, N, n_count):
    """
    Shor's period-finding circuit skeleton.
    Modular exponentiation must be implemented
    for specific (a, N) pairs.
    """
    p = Program()
    ro = p.declare('ro', 'BIT', n_count)

    # Counting register superposition
    for i in range(n_count):
        p += H(i)

    # Work register |1>
    p += X(n_count)

    # Controlled modular exponentiation
    # ... (problem-specific gates)

    # Inverse QFT (decomposed into gates)
    # ... (sequence of controlled-phase and H gates)

    for i in range(n_count):
        p += MEASURE(i, ro[i])
    return p

Implementation Note

The modular exponentiation step (\(a^x \bmod N\)) is the most complex part of Shor’s algorithm to implement. For small examples (factoring 15 or 21), the circuit can be hard-coded. For general \(N\), you need reversible modular arithmetic circuits (addition, multiplication, exponentiation), which significantly increase the gate count.

Shor’s Factoring Algorithm

Contents

Shor’s Factoring Algorithm#

The Problem#

The Reduction: Factoring to Period-Finding#

The Quantum Part: Period-Finding#

Resource Estimates#

Threat to Cryptography#

Implementations#

Further Reading#