Shor's Algorithm: Quantum Factoring Explained

Shor's algorithm factors large integers in polynomial time - a task that takes classical computers sub-exponential time. Because RSA and other public-key cryptosystems depend on factoring being hard, Shor's algorithm is the most consequential quantum algorithm for cybersecurity, even though large-scale implementation is still years away.

Quantum entanglement visualisation - the key resource in Shor's algorithm for factoring large numbers

How Shor's algorithm works

The algorithm is a hybrid: most of the clever quantum work reduces factoring to a period-finding problem, which a quantum Fourier transform solves efficiently. The steps, simplified:

1

Reduce factoring to period finding

Choose a random integer a that shares no factors with N (the number to factor). Consider the function f(x) = a^x mod N. This function is periodic - it repeats with some period r. If you can find r, you can often factor N using classical number theory (with high probability).

2

Quantum Fourier Transform for period finding

The quantum Fourier transform (QFT) is the engine of Shor's algorithm. It takes a superposition of function values and extracts the period exponentially faster than classical discrete Fourier transform methods. This is the step where quantum speedup happens - the QFT runs in O(n^2) quantum gates versus O(n * 2^n) for a classical DFT.

3

Classical post-processing

Once the period r is known, classical math takes over. If r is even and a^(r/2) is not -1 mod N, then gcd(a^(r/2) +/- 1, N) yields non-trivial factors of N with high probability. If not, restart with a different random a - the algorithm succeeds quickly on average.

Why Shor's algorithm matters for cryptography

Modern internet security rests on the difficulty of factoring large numbers and computing discrete logarithms. Shor's algorithm solves both problems efficiently.

RSA

RSA key pairs are generated from two large primes. Security depends on the difficulty of factoring their product N. Shor's algorithm factors N in polynomial time, recovering private keys from public keys.

Elliptic curve cryptography

ECDSA and ECDH use the discrete logarithm problem on elliptic curves. Shor's algorithm solves the elliptic curve discrete logarithm problem too, breaking ECC-based key exchange and signatures.

"Harvest now, decrypt later"

Adversaries can record encrypted traffic today and decrypt it once quantum computers are capable. Long-lived sensitive data - government secrets, financial records, health data - is already at risk from this strategy.

Post-quantum cryptography response

NIST finalized post-quantum standards in 2024: CRYSTALS-Kyber, CRYSTALS-Dilithium, and SPHINCS+. These are based on lattice and hash problems, not factoring - they remain secure against Shor's algorithm.

Courses covering Shor's algorithm

Quantum computing courses that include Shor's algorithm in their curriculum.

Shor's algorithm tutorials

Hands-on implementations and deep dives into the quantum Fourier transform and period finding.

Frequently asked questions

What is Shor's algorithm?
Shor's algorithm, developed by Peter Shor in 1994, factors large integers in polynomial time on a quantum computer. Classically, no known polynomial-time factoring algorithm exists - the best classical algorithms are sub-exponential but far slower. Shor's algorithm runs in O((log N)^3) time, making it exponentially faster than classical approaches for large numbers.
Can Shor's algorithm break RSA?
In principle, yes - with a sufficiently large fault-tolerant quantum computer. RSA relies on the hardness of factoring large semiprime numbers (products of two large primes). Shor's algorithm solves this efficiently. However, breaking 2048-bit RSA would require thousands of logical qubits with error correction - estimates range from a few thousand to several million physical qubits depending on hardware quality. Current quantum computers cannot run Shor's at cryptographically relevant scale.
How many qubits does Shor's algorithm need?
To factor an N-bit number, Shor's algorithm requires approximately 2N qubits at minimum for the quantum Fourier transform register, plus ancilla qubits for modular arithmetic. Factoring 2048-bit RSA keys would require thousands of logical qubits. With realistic error correction overhead, this translates to millions of physical qubits on current hardware architectures - far beyond what exists today.
Has Shor's algorithm been run on a real quantum computer?
Yes, but only on small toy examples. The largest number factored using Shor's algorithm on quantum hardware has been in the range of 21 (= 3 x 7) to a few hundred - trivial numbers that any classical calculator handles instantly. IBM, Google, and academic groups have demonstrated the algorithm's mechanics, but not at any scale that threatens cryptography. Cryptographically relevant factoring is decades away on current hardware trajectories.
What is post-quantum cryptography?
Post-quantum cryptography (PQC) refers to classical cryptographic algorithms designed to remain secure against both classical and quantum computers. NIST completed its PQC standardization process in 2024, selecting algorithms based on lattice problems (CRYSTALS-Kyber for key encapsulation, CRYSTALS-Dilithium for signatures) and hash-based signatures (SPHINCS+). These are not vulnerable to Shor's algorithm. Organizations are now beginning migration planning, especially for long-lived encrypted data.