Shor's Algorithm

Overview

Shor's algorithm is the most famous quantum algorithm, and the main reason governments and companies are migrating to new encryption. It factors a large integer into its prime factors in a number of steps that grows only polynomially with the number of digits, while the best known classical method, the general number field sieve, takes sub-exponential time. The same idea also computes discrete logarithms, which breaks the elliptic-curve and Diffie-Hellman systems used across the internet.

Nothing on the market today can run Shor's algorithm on a number large enough to matter. The importance of the algorithm is that it shows a real, practical problem with a clear quantum speedup, and that it makes the security of today's public-key cryptography depend on how fast quantum hardware improves.

The problem it solves

Finding the prime factors of a large composite number — believed to be intractable for classical computers at scale.

History and background

Peter Shor, then at Bell Labs, presented the algorithm at the IEEE Symposium on Foundations of Computer Science in 1994, and a longer version appeared in the SIAM Journal on Computing in 1997. Shor has said he was inspired by Daniel Simon's earlier algorithm, which also finds a hidden period using quantum interference. Within months the result changed quantum computing from a theoretical curiosity into a subject of national-security interest.

The first experimental demonstration came in 2001, when an IBM team used a seven-qubit nuclear magnetic resonance machine to factor 15 into 3 and 5. In 2012 photonic experiments factored 21. Critics pointed out that such tiny demonstrations used shortcuts that required knowing the answer in advance, so they say little about real capability. In 2019 Craig Gidney and Martin Ekerå estimated that RSA-2048 could be broken in about eight hours with roughly 20 million noisy qubits, and in 2025 Gidney reduced the estimate to under one million noisy qubits running for less than a week. In 2023 Oded Regev proposed a related multidimensional algorithm that reduces the gate count at the cost of more qubits.

How it works

Transforms factoring into a period-finding problem, solved efficiently using the Quantum Fourier Transform, then recovers factors via classical post-processing.

Shor's algorithm turns factoring into a different problem: finding the period of a function. Choose a random number a that shares no factors with N, and consider the sequence a, a squared, a cubed, and so on, each taken modulo N. This sequence eventually repeats, and the smallest r with a to the power r equal to 1 modulo N is called the order. If r is even and a to the r over 2 is not congruent to minus 1, then the greatest common divisor of N with a to the r over 2 plus or minus 1 reveals a nontrivial factor. The reduction is purely classical number theory.

Finding r is the hard part for a classical computer, and it is exactly what a quantum computer does well. The quantum part prepares a superposition of many exponents x, computes a to the x modulo N into a second register, and then applies the quantum Fourier transform to the first register. Different values of x that give the same function value interfere, and the Fourier transform makes only frequencies that are multiples of 1 over r survive. Measuring the register yields a number close to a multiple of 2 to the t divided by r, from which the continued fractions method recovers r.

No single step is a quantum speedup of a classical computation in the naive sense of trying all answers at once. The power comes from interference: amplitudes for wrong periods cancel, and amplitudes for the right period reinforce. That is why the algorithm needs the exact structure of modular exponentiation and cannot be applied to arbitrary problems.

Step by step

1. Pick a random integer a between 2 and N minus 1. If the greatest common divisor of a and N is not 1, you have already found a factor and can stop.
2. Prepare two quantum registers: a counting register of about 2n qubits, where n is the bit length of N, and a work register of n qubits in the state 1. Apply Hadamard gates to the counting register to create an equal superposition of all exponents.
3. Apply a controlled modular exponentiation that maps each exponent x to a to the x modulo N in the work register. This is the most expensive part of the circuit.
4. Measure the work register, or simply ignore it. The counting register is left in a superposition of exponents spaced r apart.
5. Apply the inverse quantum Fourier transform to the counting register and measure it to obtain a number y.
6. Use the continued fractions algorithm on y divided by 2 to the t to find a candidate period r.
7. Check that r is even and that a to the r over 2 is not minus 1 modulo N. If so, compute the greatest common divisors of N with a to the r over 2 plus 1 and minus 1 to obtain factors. If not, repeat with a new a. A random choice of a works with probability of at least one half.

A worked example

Take N = 15 and a = 7. The powers of 7 modulo 15 are 7, 4, 13, 1, and then the pattern repeats, so the order is r = 4. Because r is even, compute 7 to the power 2, which is 49 and equals 4 modulo 15. Then the greatest common divisor of 4 minus 1 and 15 is 3, and the greatest common divisor of 4 plus 1 and 15 is 5. The factors of 15 are 3 and 5.

On a quantum computer, the order r = 4 is found by sampling. With an 8-qubit counting register, the Fourier transform peaks at multiples of 256 divided by 4, namely 0, 64, 128, and 192. Measuring any nonzero peak, such as 64, gives 64 over 256, which is one quarter, and the denominator of that fraction is 4. For realistic numbers the same logic is applied to registers with thousands of qubits.

Complexity and resources

What hardware it needs

• A fault-tolerant quantum computer with thousands of logical qubits and billions of gates, because the circuit is deep and any uncorrected error ruins the interference pattern.
• Fast, reliable quantum error correction with low enough physical error rates, around 0.1% or better, and real-time decoding.
• Many repetitions of the circuit, since each run gives only a candidate period that has to be checked.

Applications

• Breaking RSA, Diffie-Hellman, and elliptic-curve cryptography, which protect web traffic, digital signatures, and software updates.
• Computing discrete logarithms in groups, which is the same hidden-period structure.
• Motivating the migration to post-quantum cryptography and driving the harvest-now-decrypt-later concern.
• Serving as the standard benchmark for fault-tolerant quantum computing resource estimates.

Limitations and caveats

• It only offers an advantage for problems with a hidden periodic structure, and it does not speed up factoring-unrelated tasks.
• Small demonstrations such as factoring 15 or 21 usually exploit precompiled knowledge of the answer, so they are not evidence of scalable capability.
• The circuit needs millions of physical qubits with current error rates, far beyond what exists today.
• Symmetric encryption such as AES and hash functions are not broken by it.

Common misconceptions

• It does not try all factors in parallel. The speedup comes from interference that isolates the period of a function.
• It does not threaten all encryption. Symmetric ciphers and hash-based signatures are largely unaffected.
• Having factored 15 does not mean a quantum computer is close to breaking RSA. The gap is many orders of magnitude.

How it compares

• Grover's algorithm gives only a quadratic speedup for unstructured search, while Shor's gives a super-polynomial speedup for a structured problem.
• Simon's algorithm is the direct ancestor: it finds a hidden XOR period, while Shor finds a hidden arithmetic period.
• Compared with lattice-based post-quantum schemes, factoring has no known efficient quantum algorithm for lattice problems, which is why they are the replacement.

Real-world impact

Directly motivates post-quantum cryptography; would break RSA and similar encryption if run on a large enough fault-tolerant quantum computer.

Why it matters

Shor's algorithm is the clearest example of a quantum computer solving a problem that matters to the real world. It is the reason the US National Institute of Standards and Technology published post-quantum standards in 2024, including ML-KEM for key exchange and ML-DSA and SLH-DSA for signatures, and why many governments set deadlines for migrating.

It also shapes the timeline for the whole field. Resource estimates for RSA-2048 are a common yardstick for hardware roadmaps, and every drop in the estimated qubit count moves the date at which a large quantum computer could become a security risk closer.

Frequently asked questions

Keep learning

• Read the full deep-dive in our Learning Center
• Related algorithm: Quantum Fourier Transform (QFT)
• Related algorithm: Quantum Phase Estimation (QPE)
• Related algorithm: Simon's Algorithm
• Related algorithm: Grover's Algorithm

This page is written for educational purposes. Complexity statements describe the best known results at the time of review (September 30, 2026), and research in this area moves quickly, so check recent papers before relying on a specific bound.

← Back to Algorithms Database