Hadamard Get the app

How Does Shor’s Algorithm Work? Factoring 15 and 21 Step by Step

How Does Shor's Algorithm Work? Factoring 15 and 21 Step by Step — Hadamard

How does Shor’s algorithm work? It turns factoring a number N into a different problem: finding the period, or “order”, of the sequence a, a², a³, … modulo N. A quantum computer finds that period efficiently, and a few classical steps with greatest common divisors (gcd) turn the period into factors of N.

Only one step is quantum. Everything else is number theory you can do with pencil and paper. This article walks through both parts, works N = 15 and N = 21 by hand, and explains why running the algorithm on small numbers is still far from breaking RSA.

How does Shor’s algorithm work? The short version

Peter W. Shor, then at AT&T Research, wrote “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer”. A preliminary version appeared at the 35th Annual Symposium on Foundations of Computer Science (FOCS) in Santa Fe, November 20–22, 1994, according to the paper’s own footnote. The arXiv version was first submitted on 30 August 1995. The journal version appeared in SIAM Journal on Computing 26 (1997) 1484.

The abstract states the claim plainly: “Efficient randomized algorithms are given for these two problems on a hypothetical quantum computer.” The two problems are factoring and discrete logarithms. The paper also names its target directly: “the widely used RSA public key cryptosystem developed by Rivest, Shamir, and Adleman.” If you want the background on RSA itself, see our article on who invented public-key cryptography.

At a high level the algorithm has three stages:

  1. Classical reduction: pick a random number a and turn “factor N” into “find the order of a modulo N”.
  2. Quantum order finding: use phase estimation on a modular multiplication circuit to get a fraction close to k/r, where r is the order.
  3. Classical post-processing: recover r with continued fractions, then compute a gcd to get a factor.

The number theory: order finding and the gcd trick

IBM’s course Fundamentals of quantum algorithms defines the core problem like this. You are given N and a number a with gcd(N, a) = 1. Find the smallest positive integer r such that ar ≡ 1 (mod N). That r is the order of a modulo N.

Why does the order help? If r is even, then ar − 1 = (ar/2 − 1)(ar/2 + 1) is divisible by N. As long as neither factor on the right is a multiple of N on its own, each one shares a nontrivial factor with N, and a gcd pulls it out.

IBM gives the reduction for N odd, composite and not a prime power:

  1. Pick a random a in {2, …, N−1}.
  2. If d = gcd(a, N) > 1, d is already a factor. Stop.
  3. Otherwise, find the order r of a modulo N. This is the quantum step.
  4. If r is even, compute d = gcd(ar/2 − 1, N). If d > 1, output d and N/d.
  5. Otherwise the run fails. Pick a new a and try again.

Each run succeeds with probability “at least 1/2”, so t independent runs succeed with probability at least 1 − 2−t. Even N and prime powers are easy to handle classically, so they are dealt with separately.

Shor’s paper gives the same condition from the other direction. The procedure fails only when r is odd or when xr/2 ≡ −1 (mod n). For a random x, it yields a nontrivial factor with probability at least 1 − 1/2k−1, where k is the number of distinct odd prime factors of n.

Shor’s algorithm factoring 15 example (and 21)

N = 15 with a = 7

Compute the powers of 7 modulo 15:

  • 71 ≡ 7
  • 72 = 49 ≡ 4
  • 73 ≡ 4 · 7 = 28 ≡ 13
  • 74 ≡ 13 · 7 = 91 ≡ 1

So r = 4, which is even. Then 7r/2 = 72 ≡ 4 (mod 15). That gives gcd(4 − 1, 15) = 3 and gcd(4 + 1, 15) = 5. Indeed, 15 = 3 × 5.

Which choices of a work for 15?

The same arithmetic for every a that is coprime to 15 shows how often a run succeeds:

a Powers mod 15 Order r ar/2 mod 15 Result
2 2, 4, 8, 1 4 4 gcd(3, 15) = 3, gcd(5, 15) = 5
4 4, 1 2 4 3 and 5
7 7, 4, 13, 1 4 4 3 and 5
8 8, 4, 2, 1 4 4 3 and 5
11 11, 1 2 11 gcd(10, 15) = 5, gcd(12, 15) = 3
13 13, 4, 7, 1 4 4 3 and 5
14 14, 1 2 14 ≡ −1 Fails: xr/2 ≡ −1

Only a = 14 hits the failure case Shor describes. For values of a that share a factor with 15, such as 6 (gcd 3) or 10 (gcd 5), step 2 finds a factor without any quantum work.

N = 21 with a = 2

IBM’s course uses N = 21. The powers of 2 modulo 21 are 2, 4, 8, 16, 11, 1, so the order of 2 is 6. Then 23 = 8, gcd(8 − 1, 21) = gcd(7, 21) = 7, and 21/7 = 3.

For numbers this small, listing powers is trivial. For a 2048-bit N the order can be astronomically large, and no known classical method finds it efficiently. That step is the one handed to the quantum computer.

What the quantum part of Shor’s algorithm does

The quantum step uses a circuit for the operation Ma|x⟩ = |ax mod N⟩. Multiplying by a modulo N is reversible when gcd(a, N) = 1, so Ma is a unitary operation. According to IBM’s course, its eigenvectors |ψk⟩ have eigenvalues e2πik/r. The order r is hidden in those phases.

Phase estimation

Quantum phase estimation reads out an eigenvalue’s phase. A register of m control qubits is put into superposition (with Hadamard gates, named after the mathematician Jacques Hadamard). The control qubits then apply Ma raised to powers 1, 2, 4, 8, and so on, to a second register. An inverse quantum Fourier transform converts the result into a number y that you can measure. The output y/2m approximates k/r.

Preparing a specific eigenvector would require already knowing r. The trick is to start the second register in |1⟩. IBM’s course notes that |1⟩ is an equal superposition of all the eigenvectors: |1⟩ = (1/√r) Σk |ψk⟩. Each measurement therefore gives y/2m ≈ k/r for a uniformly random k between 0 and r − 1.

IBM also points out that Shor did not originally describe the algorithm as phase estimation. Framing it that way is simply a natural way to explain it.

For N = 15 and a = 7, where r = 4, the possible outcomes are k/r = 0, 1/4, 1/2 and 3/4. An outcome of 0 tells you nothing. An outcome of 1/2 suggests r = 2, which is only a divisor of the true order. Outcomes of 1/4 or 3/4 reveal r = 4 directly.

Getting r back out: continued fractions and repeated runs

For most N, the measured y/2m is only close to k/r, not equal to it. The continued fraction expansion finds the best simple fraction u/v near the measured value, which equals k/r in lowest terms. If k and r share a factor, v is only a divisor of r. So you repeat the run a few times. IBM’s course says the least common multiple of the denominators gives a good guess for r, and the chance of error falls exponentially with the number of samples.

Precision matters. IBM states that m = 2·lg(N) + 1 control qubits gives “a high chance” of success, and m = 2·lg(N) gives “a lower bound of 40%”. Its example uses r = 6:

  • With 5 control qubits, the best approximation to 1/6 is 5/32, and 32/5 = 6.4 rounds correctly to 6.
  • With 4 control qubits, you get 3/16, and 16/3 ≈ 5.33 rounds wrongly to 5.

Once a candidate r is found, checking it is easy: compute ar mod N classically and see whether it equals 1.

How fast is Shor’s algorithm compared with classical factoring?

Shor’s paper gives the quantum cost as O((log n)2 · log log n · log log log n) steps, plus classical post-processing that is polynomial in log n. The comparison point is the number field sieve, the best classical method, which runs in exp(c(log n)1/3(log log n)2/3).

The paper adds an important framing point: “Since the input, n, is only log n bits in length, this algorithm is an exponential-time algorithm.” Measured against the bit length of the number, the sieve grows faster than any polynomial. Shor’s algorithm grows only polynomially.

IBM’s course gives a more conservative accounting with textbook arithmetic. In terms of the bit length n, the controlled-unitary part costs O(n3), the whole quantum procedure is O(n3), and the classical work is O(n3). Faster multiplication algorithms can improve these bounds. IBM’s blog notes that no known classical algorithm factors in polynomial time, although some run in sub-exponential time.

What has actually run on hardware, and why scale matters

15 in 2001

In 2001, a team at IBM Almaden and Stanford (L. M. K. Vandersypen, M. Steffen, G. Breyta, C. S. Yannoni, M. H. Sherwood and I. L. Chuang) factored 15 into 3 and 5. They used seven spin-1/2 nuclei in a single molecule, controlled by room-temperature liquid-state NMR. The result was published in Nature 414, 883–887. The authors stated that their work does not show the approach scales.

IBM’s 2022 retrospective adds that the molecule was a “perfluorobutadienyl iron complex”. Early runs showed 3 and 5 plus extra signals, which the team traced mainly to decoherence. Chuang said factoring 15 on current hardware “assumes some amount of simplification”, and that a version that scales to larger numbers is a much better test.

21 in 2012

A Bristol team (Martín-López, Laing, Lawson, Álvarez, Zhou and O’Brien) factored 21 with a two-photon compiled algorithm. They reused a single control qubit n times, which needed one third of the qubits of the standard protocol. The work appeared in Nature Photonics 6, 773–776 (2012).

From 21 to RSA-2048

The gap between these demonstrations and real keys is large. In a May 2025 preprint, Craig Gidney estimates that RSA-2048 could be factored with fewer than one million noisy qubits in under a week. The earlier estimate by Gidney and Ekerå (2019) was about 20 million qubits and about eight hours. Both assume a 0.1% gate error rate, a 1 µs surface-code cycle and a 10 µs reaction time. Most of those qubits go to error correction. The algorithm needs long, reliable runs of modular arithmetic, and today’s hardware cannot yet sustain that.

The same idea also solves discrete logarithms, which is why elliptic-curve signatures such as ECDSA are in scope. Hadamard builds BB84, an Ethereum Layer 2 rollup whose accounts use hash commitments instead of ECDSA keys, for exactly this reason. You can follow how other systems are handling the transition in our post-quantum migration tracker.

FAQ

Is Shor’s algorithm mostly quantum or classical?

Mostly classical. Only order finding runs on the quantum computer. Choosing a, the gcd checks, the reduction from factoring to order finding, and the continued fraction step are all ordinary classical computation.

Why do demonstrations always factor 15 or 21?

Because they rely on compiled or simplified circuits that already use knowledge of the answer’s structure, and current hardware cannot run the full algorithm on larger numbers. Isaac Chuang has said that factoring 15 “assumes some amount of simplification”, and that a scalable version is the better test.

Does Shor’s algorithm break all cryptography?

No. It breaks factoring and discrete logarithms, which covers RSA, Diffie-Hellman and elliptic-curve cryptography. It does not break hash functions. Those face Grover-style attacks, which are much weaker, as explained in Can Quantum Computers Break SHA-256?

What happens if the order r is odd?

That run fails, and you pick a new random a and try again. The same applies if ar/2 ≡ −1 (mod N). Each run succeeds with probability at least 1/2, so a handful of runs is almost always enough.

Sources