Case Study: Auditing a 'We Factored a Large Number' Claim
Executive Summary
Every few years a paper or press release announces the quantum factorization of a number far larger than 21 — 143, 291311, or in one widely covered case a 48-bit integer using ten qubits. Each time, cryptographers respond with a collective sigh, and each time the coverage suggests RSA is closer to falling.
None of these results used Shor's algorithm as specified, and none of them scale. This case study builds the audit: the four ways a factoring demonstration can be simplified into meaninglessness, how to detect each, and what a genuine result would look like.
Skills applied
- Identifying the components a genuine Shor implementation requires (§15.6).
- Recognizing pre-compilation and answer-dependent circuits (§15.13).
- Distinguishing Shor from adiabatic and annealing-based factoring.
- Estimating the qubit count a claim implies and checking it for consistency.
Phase 1: What a genuine implementation must contain
Shor's algorithm has four parts. All four must be present and general:
- Classical reduction — pick random $a$, check $\gcd(a,N)$.
- Quantum period finding — superposition over $2^t \ge N^2$ values of $x$, then $|x\rangle|0\rangle \mapsto |x\rangle|a^x \bmod N\rangle$.
- Inverse QFT on the counting register, then measure.
- Continued fractions to recover $r$, then $\gcd(a^{r/2}\pm1, N)$.
The load-bearing requirement is that step 2 must implement $a^x \bmod N$ as a general reversible circuit, without using knowledge of $r$ or of the factors. This is where nearly every demonstration departs from the algorithm.
Phase 2: The four simplifications
Simplification 1 — answer-dependent compilation. The circuit is optimized using the known factorization. If you know $r$ in advance, most of the modular-exponentiation circuit is provably redundant and can be removed. The resulting circuit produces the right answer and can factor exactly one number: the one you already knew.
Detection: ask whether the same circuit, unmodified, would run on a different $N$ of the same size. If not, it is a demonstration of circuit compilation, not of factoring.
Simplification 2 — a convenient base $a$. Choosing $a$ with period $r = 2$ or $4$ collapses period finding to a trivial circuit. Genuine Shor picks $a$ at random and must handle whatever period results.
Detection: check whether $a$ was chosen randomly or selected. Check the period's size relative to $N$.
Simplification 3 — qubit-count arithmetic that does not add up. A faithful implementation needs roughly $2n$ qubits for the counting register plus $n$ or more for the work register — call it $3n$ minimum, with realistic implementations using $5n$ or more. A claim to factor a 48-bit number with 10 qubits implies $3n = 144$ qubits minimum. Ten is not 144.
Detection: compute $3n$ and compare against the reported qubit count. This single arithmetic check disposes of most claims in under a minute.
Simplification 4 — a different algorithm entirely. Several results use adiabatic optimization or quantum annealing: encode factoring as minimizing $(N - pq)^2$ over bit variables, then anneal. This is a legitimate technique and it is not Shor's algorithm — it has no proven speedup, and its cost scaling is empirical and poor. Reports of annealing-based factorization of large numbers describe a heuristic search, not a polynomial-time algorithm.
Detection: look for the words adiabatic, annealing, QUBO, or Ising. If the QFT is absent, it is not Shor.
Phase 3: Working an example
A hypothetical announcement:
"Using a 5-qubit processor, we factored 35 = 5 × 7 via Shor's algorithm, demonstrating scalability toward cryptographically relevant sizes."
Audit:
| Check | Value | Verdict |
|---|---|---|
| $n = \lceil\log_2 35\rceil$ | 6 bits | — |
| Minimum qubits ($\approx 3n$) | 18 | 5 reported — fails |
| Counting register $2^t \ge N^2 = 1225$ | $t \ge 11$ | Cannot fit in 5 qubits |
| General modular exponentiation? | Not possible in 5 qubits | Fails |
| Scalability claim | — | Unsupported |
The result is real in the sense that the device ran a circuit and produced 5 and 7. It is not a factorization in the algorithmic sense, and the scalability claim is the opposite of what the qubit arithmetic shows.
Phase 4: What the honest record is
Genuine, non-simplified implementations have factored 15 and 21. That is the state of the art, and it has not moved much in two decades — not because researchers lack ingenuity but because the circuits require coherence far beyond current hardware.
The gap to RSA-2048:
| Qubits (logical) | Modular exp. gates | Physical qubits | |
|---|---|---|---|
| $N = 15$ | ~8 | ~10² | ~8 |
| $N = 21$ | ~10 | ~10² | ~10 |
| RSA-2048 | ~6,000 | ~$10^{10}$ | ~$2\times10^{7}$ |
Six orders of magnitude in logical qubits, eight in gate count.
Phase 5: What a genuine advance would look like
The signals worth paying attention to, in increasing order of significance:
- Factoring a number whose factorization was not used to build the circuit — at any size, even 35, if genuinely general.
- A demonstration of general modular exponentiation on an encoded register, error-corrected.
- Logical qubit counts entering the thousands with error rates supporting $10^{10}$-gate circuits.
- A published end-to-end resource estimate that shrinks materially — the Gidney–Ekerå line of work is the one to track, and improvements there move the timeline more than hardware announcements do.
Notably, none of these look like a press release about factoring a big number.
Discussion Questions
- Answer-dependent compilation produces a circuit that outputs the right factors. In what sense has it "not factored" the number?
- The $3n$-qubit check disposes of most claims. Why is it so rarely applied in press coverage?
- Annealing-based factoring is legitimate research. Why is reporting it as progress toward breaking RSA misleading?
- The record has been stuck at 15 and 21 for two decades. Is that evidence the threat is overstated? Argue both sides.
Your Turn: Extensions
- Implement Shor for $N = 15$ with $a = 7$ and confirm the period $r = 4$ appears in the measurement histogram.
- Count the qubits your implementation needs and compare against $3n$.
- Deliberately build an answer-dependent circuit for $N=21$ and observe how much smaller it is.
- Find a published large-number factoring claim and run the four-check audit on it.
Key Takeaways
- A genuine Shor implementation requires general modular exponentiation that does not depend on knowing the answer; almost every headline factoring result violates this.
- The $\approx 3n$ qubit floor is a one-minute arithmetic check that invalidates most claims.
- Annealing and adiabatic factoring are different algorithms with no proven speedup; the absence of a QFT is the tell.
- The honest record for non-simplified Shor remains 15 and 21, six orders of magnitude from RSA-2048.
- Meaningful progress will appear as improved resource estimates and error-corrected logical qubit counts, not as larger factored numbers.