Shor's Algorithm

Shor’s Algorithm

Definition: A quantum algorithm that factors large numbers exponentially faster than the best known classical algorithms, famous for threatening the mathematical foundation of widely used public-key encryption.

How It Works

Exploits Superposition and quantum gates to find the period of a mathematical function far faster than classical methods, finding that period is the key step that makes factoring large numbers tractable.
Factoring N is reduced to a period-finding problem: pick a random integer a coprime to N, then find the period r of the function f(x) = a^x mod N, the smallest r such that a^r ≡ 1 (mod N).
The quantum part uses the Quantum Fourier Transform (QFT) to extract the period r from a superposition of f(x) values, a task exponentially hard for classical computers as N grows large, but efficient on a quantum computer.
Once r is found, classical post-processing computes gcd(a^(r/2) - 1, N) and gcd(a^(r/2) + 1, N), the greatest common divisors, which (with good probability) yield two nontrivial factors of N.
The algorithm can fail on a given random a, if r turns out odd, or if a^(r/2) ≡ -1 (mod N), in which case you simply pick a new random a and retry, the expected number of retries is small.
On a large enough, sufficiently reliable quantum computer, it could factor the huge numbers underlying RSA encryption in a practical amount of time, versus the effectively-impossible timeframes classical computers face using the best known classical factoring method (the general number field sieve).
Currently limited by hardware: no existing quantum computer has enough stable, low-error, fully error-corrected logical qubits to run it against real-world-sized encryption keys (RSA-2048 needs roughly 20 million noisy physical qubits by some estimates, far beyond current hardware).
The same period-finding technique generalizes beyond factoring: a variant solves the discrete logarithm problem, which is what makes Shor’s Algorithm a threat to elliptic-curve cryptography and Diffie-Hellman key exchange too, not just RSA.
The Quantum Fourier Transform at the algorithm’s core is itself an exponential speedup over the classical Fast Fourier Transform, it’s a reusable building block that shows up in several other quantum algorithms beyond Shor’s.

Under the Hood

The core reduction: factoring N becomes finding the period r of:

f(x) = a^x mod N

Then classically:

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

Given: N = 15, and a randomly chosen a = 7. Step: find the period r of f(x) = 7^x mod 15: 7^1=7, 7^2=4, 7^3=13, 7^4=1, so r = 4. Answer: r is even, and a^(r/2) = 7^2 mod 15 = 4, which is not -1 mod 15 (14), so it’s valid. Compute gcd(4-1, 15) = gcd(3,15) = 3, and gcd(4+1, 15) = gcd(5,15) = 5. Factors: 15 = 3 × 5, correct.

Given: the same N = 15, but with a = 4 chosen instead. Step: find the period of f(x) = 4^x mod 15: 4^1=4, 4^2=1, so r = 2. Answer: r is even, a^(r/2) = 4^1 = 4 mod 15, not -1 mod 15, valid. gcd(4-1,15) = gcd(3,15) = 3, gcd(4+1,15) = gcd(5,15) = 5, again correctly recovers 3 and 5, different valid choices of a can lead to the same or different discovery paths.

Given: RSA-2048, a 2048-bit modulus, roughly 617 decimal digits. Step: compare classical general number field sieve cost, sub-exponential in the number of bits, against Shor’s algorithm’s polynomial-time cost. Answer: classical factoring of RSA-2048 is estimated to take longer than the age of the universe with current techniques and hardware, while Shor’s algorithm on a sufficiently large fault-tolerant quantum computer would need roughly polynomial time in the number of bits, the qualitative gap between infeasible and feasible is the entire reason the algorithm matters strategically.

Given: N = 21, and a = 2 chosen as the base. Step: find the period of f(x) = 2^x mod 21: 2^1=2, 2^2=4, 2^3=8, 2^4=16, 2^5=11, 2^6=1, so r = 6. Answer: r is even, a^(r/2) = 2^3 mod 21 = 8, not -1 mod 21 (20), valid. gcd(8-1,21)=gcd(7,21)=7, gcd(8+1,21)=gcd(9,21)=3, factors: 21 = 3 × 7, correct, and this exact case (N=21) was physically demonstrated on quantum hardware in 2012.

Given: a naive classical brute-force period search for the same a=7, N=15 example. Step: compare the classical approach (computing a^x mod N for increasing x until it cycles) to the quantum QFT-based approach. Answer: classically, this brute-force search is exponential in the number of bits of N for large N; the quantum version finds the period using a superposition over all x values simultaneously and a single QFT, achieving the same result in polynomial time, this contrast is the entire source of the exponential speedup.

Why It Matters

The single biggest reason governments and companies are investing heavily in “post-quantum cryptography,” encryption designed to run on classical computers but resist attack by a future quantum computer capable of running Shor’s Algorithm at scale.
NIST finalized its first post-quantum cryptography standards in 2024 (ML-KEM, ML-DSA, and others), a direct, concrete response to the long-term threat Shor’s Algorithm poses to RSA and elliptic-curve cryptography.
“Harvest now, decrypt later” is a real present-day concern: adversaries can record encrypted traffic today and decrypt it once a capable quantum computer exists years from now, which is why migration to post-quantum algorithms is being pushed well ahead of any working large-scale quantum factoring machine.
It’s the clearest, most consequential proof that quantum computers aren’t just faster classical computers, they can be asymptotically better at specific problems that underpin real-world infrastructure.
Organizations like NSA and NIST have published explicit timelines urging migration to post-quantum algorithms well before any confirmed cryptographically relevant quantum computer exists, treating the algorithm’s eventual threat as a planning certainty rather than a maybe.

Common Pitfalls

Believing current encryption is already broken. Today’s quantum hardware is nowhere near capable of running Shor’s Algorithm against real-world key sizes, demonstrations so far have only factored small numbers like 15 or 21.
Confusing the theoretical threat (a sufficiently powerful future quantum computer) with an immediate, present-day risk to deployed systems, the timeline for a cryptographically relevant quantum computer remains genuinely uncertain, likely a decade or more away by most expert estimates.
Assuming Shor’s Algorithm threatens all encryption equally. It specifically breaks cryptosystems based on integer factorization (RSA) and discrete logarithms (Diffie-Hellman, elliptic-curve cryptography), symmetric encryption like AES is only weakened quadratically by a different algorithm (Grover’s Algorithm), not broken outright.
Thinking the algorithm “guesses” factors probabilistically in a weak sense. It’s a deterministic reduction (factoring to period-finding) with a quantum subroutine that succeeds with high, well-characterized probability per attempt, not a heuristic search.
Underestimating the qubit and error-correction requirements. Running Shor’s Algorithm on RSA-2048 is estimated to need millions of physical qubits once error correction overhead is included, several orders of magnitude beyond current hardware.
Assuming a bigger quantum computer by qubit count alone gets closer to running Shor’s Algorithm usefully. What matters is logical, error-corrected qubit count and circuit depth, not the raw noisy physical qubit count vendors often headline.
Forgetting the algorithm is probabilistic per attempt, not per problem. A “failed” run (odd r, or a bad choice of a) isn’t a bug, it’s an expected outcome that simply requires retrying with a new random a, the overall expected number of attempts is small and well understood.

Comparison

	Classical factoring (GNFS)	Shor’s Algorithm	Grover’s Algorithm
Speedup type	N/A, baseline	Exponential over classical	Quadratic over classical
Problem solved	Integer factorization	Integer factorization, discrete log	Unstructured search
Threatens	N/A	RSA, Diffie-Hellman, ECC	Symmetric ciphers, weakly
Practical status today	Runs on classical hardware now	Needs fault-tolerant qubits, not yet available	Needs many stable qubits, not yet practical at scale

Post-Quantum Response Timeline

Milestone	Year	Significance
Shor publishes the algorithm	1994	First proof a quantum computer could break RSA-style cryptography
First physical demonstration (N=15)	2001	IBM’s NMR-based 7-qubit experiment
NIST post-quantum competition begins	2016	Global search for quantum-resistant classical algorithms
NIST finalizes first PQC standards	2024	ML-KEM, ML-DSA, and SLH-DSA published as official standards
Major browsers/apps adopt PQC	2023-2025	Chrome, Signal, and others roll out hybrid classical-PQC key exchange

Cryptosystems at Risk

Cryptosystem	Underlying hard problem	Broken by Shor’s Algorithm?
RSA	Integer factorization	Yes
Diffie-Hellman	Discrete logarithm	Yes
Elliptic-curve cryptography (ECC)	Elliptic-curve discrete logarithm	Yes, via a variant
AES (symmetric)	Key-space search	No, only weakened quadratically by Grover’s
Lattice-based (e.g. ML-KEM)	Shortest/closest vector problems	No known efficient quantum attack

Example

RSA encryption, which secures much of today’s internet traffic (TLS/HTTPS, VPNs, digital signatures), relies on factoring large numbers being computationally infeasible for classical computers, exactly the assumption Shor’s Algorithm threatens once sufficiently capable quantum hardware exists.

In 2001, IBM researchers factored 15 into 3 × 5 using an early 7-qubit NMR-based quantum computer, the first physical demonstration of Shor’s Algorithm, though on a number trivial to factor classically, the demonstration proved the algorithm’s mechanics worked in real hardware.

NIST’s 2024 post-quantum cryptography standards (including ML-KEM, based on lattice problems believed hard even for quantum computers) are already being rolled out in browsers and messaging apps like Signal, a direct, ongoing industry response to Shor’s Algorithm’s long-term threat.

In 2012, researchers factored 21 using photonic qubits, at the time the largest number factored by a genuinely scalable version of the algorithm, illustrating both real progress and how far the field still had to go to threaten real key sizes.

Referenced by

Dig deeper

Spot an error in this note?