Further Reading: Shor's Algorithm

Tagged Tier 1 (confident it exists and recommended) and Tier 2 (real and worth seeking, but verify the current version or URL).

The primary sources

• Shor, "Algorithms for quantum computation: discrete logarithms and factoring" (1994 FOCS); expanded as "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer" (1997), SIAM Journal on Computing 26, 1484. The paper. Read it for the discrete logarithm half as well — it is usually omitted from teaching treatments and it is what breaks Diffie–Hellman and elliptic-curve cryptography. Shor has credited Simon's algorithm as the direct inspiration, which is Chapter 20 §20.6's point documented rather than asserted. Tier 1.
• Nielsen and Chuang, §5.3. Order finding and factoring, with the continued-fractions argument done carefully — including the bound on how many bits $t$ you need for the convergent to be guaranteed correct, which §23.3 states without proving. Tier 1.
• Hardy and Wright, An Introduction to the Theory of Numbers, on continued fractions. The classical result Shor's post-processing rests on. Reading it makes §23.3 stop feeling like a trick. Tier 1.

On what it actually costs

• Gidney and Ekerå, "How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits" (2021), Quantum 5, 433. The definitive resource estimate, and the one Chapter 15 Case Study 1 cross-checked against. Read it for the optimizations, not the number — the figure came down by more than an order of magnitude from earlier estimates through better constructions alone, and the paper shows exactly where. Exercise 23.23's subject. Tier 1.
• Beauregard, "Circuit for Shor's algorithm using 2n+3 qubits" (2003). The classic qubit-count-optimized construction, and a good entry point to the modular-arithmetic literature that §23.6 says is where all the real work is. Tier 1.
• Any current work on reversible modular multiplication and constant-factor optimizations. This is 99.92% of the circuit and correspondingly where the research effort goes. Search for reversible modular exponentiation, windowed arithmetic, and Toffoli-count optimization. Tier 2 — active, and the numbers keep improving.
• Chapter 19's oracle-cost accounting, applied here. Modular exponentiation is built from Toffolis at 7 T gates each, and Chapter 19 §19.6's ancilla trade applies directly. Tier 1.

On demonstrations, and reading them critically

• Smolin, Smith, and Vargo, "Oversimplifying quantum factoring" (2013), Nature 499, 163. The argument Case Study 1 makes, made properly: several published factoring demonstrations compile away the hard part using knowledge of the answer, and the authors show you can "factor" large numbers with a handful of qubits this way. The single most useful corrective on this topic. Tier 1.
• Any factoring demonstration you encounter, read for its modular arithmetic. The test from Case Study 1: would the circuit still work if the answer were unknown? If the construction requires $r$, it cannot be evidence about finding $r$. Tier 1 as a practice.

On the cryptographic consequences

• NIST's post-quantum cryptography standards and migration guidance. The authoritative source for what to migrate to and in what order. Read the migration guidance specifically for the data-lifetime framing — it is Case Study 2's argument in official form. Tier 1.
• Mosca's theorem / the "Mosca inequality." The migration-deadline formula stated formally: if $x$ is your data's shelf life, $y$ your migration time, and $z$ the time until a cryptographically relevant quantum computer, you are in trouble when $x + y > z$. Case Study 2's arithmetic, in the form the security community uses. Tier 1.
• The literature on hybrid key exchange. Running a post-quantum KEM alongside a classical one so an attacker must break both — the standard answer to "what if the new algorithms turn out to be flawed." Tier 1.
• Any careful treatment of "harvest now, decrypt later." The threat model that makes the deadline precede the machine. Tier 2.

On the wider picture

• Cleve, Ekert, Macchiavello, and Mosca, "Quantum algorithms revisited" (1998). Also cited in Chapter 22 — it places Shor, Simon, Grover, and Deutsch–Jozsa in one framework. Read it after this chapter rather than before; the unification lands harder once you have seen Shor work. Tier 1.
• Any survey of the hidden subgroup problem, on the non-abelian case. Shor solves the abelian case. The non-abelian case contains graph isomorphism, and has resisted a quantum algorithm for three decades — which is the strongest available evidence that quantum speedups are structural rather than general. Exercise 23.32's subject. Tier 2.

Forward references

• Chapter 24 — the deliberate change of register: algorithms designed for hardware that exists.
• Chapter 25 — what the 24.9 million physical qubits are actually doing.
• Chapter 38 — post-quantum migration, and quantum key distribution as a different answer to the same problem.
• Chapter 15 Case Study 1 — the RSA-2048 estimate, with the estimator and the cross-check.

Where to go next. If one thing: Smolin, Smith, and Vargo on oversimplified factoring. It is short, it is sharp, and it will change how you read every factoring headline afterwards — which is a more durable skill than any circuit in this chapter.

If two: add Gidney and Ekerå, read for the optimizations rather than the number. Watching an estimate drop by an order of magnitude through construction improvements alone is the best available argument for why "when will RSA fall" has no fixed answer.

Then Chapter 24 — variational algorithms, where the machine exists and the question becomes whether anything useful can be done with it.