How quantum algorithms threaten classical public-key cryptography.

The quantum threat is specific, not a blanket "quantum breaks everything." Shor's algorithm changes the difficulty class of factoring and discrete logarithms; Grover's algorithm gives a generic quadratic speedup to unstructured search. Neither statement says a present-day device can break a production key — that gap between "the algorithm exists" and "an adversary has a machine capable of running it at cryptographic scale" is exactly what this chapter is about. We connect both algorithms to their actual resource assumptions, work through tiny reproducible examples of each, learn to read a resource-estimate paper without extracting the most dramatic number from its abstract, and build a worked \(S+M>Q\) migration scenario grounded in the records service from Parts 1–2.

1. Objectives and prerequisites

Read Part 2 first if key agreement, signatures, or hash security goals feel unfamiliar. Here you only need integer arithmetic and the basic idea of a probability. By the end you'll have enough quantum vocabulary to understand the cryptographic threat precisely, work through a small order-finding reduction by hand, interpret a resource estimate without being misled by it, and build a migration scenario without ever needing to invent a quantum-arrival date.

Our records service has three separate concerns: someone may collect its encrypted traffic today, forge a future update, or steal a current endpoint's key outright. Quantum cryptanalysis changes the first two of these in genuinely important ways. It does not replace the third with some new quantum problem — endpoint compromise is endpoint compromise, quantum computer or not. A useful assessment keeps these three attack paths separate, so a quantum-migration project doesn't accidentally distract attention from an exposed signing service or an unpatched endpoint that was never a quantum problem to begin with.

2. A qubit is not an ordinary bit with an unknown value

A classical bit is observed as zero or one, full stop. A qubit instead has a state described by amplitudes associated with the basis states zero and one — complex numbers, not probabilities directly. The squared magnitudes of those amplitudes determine measurement probabilities, and the two must sum to one. Amplitudes also carry phase information, which affects how later operations combine and interfere with each other — this phase relationship is the entire mechanism both Shor's and Grover's algorithms exploit, and it has no classical-bit analogue at all.

For intuition, imagine two paths through an experiment whose contributions can reinforce or cancel each other out — that's a far more useful mental model than imagining a database secretly containing readable answers to every question at once. A superposition is manipulated by operations on the whole state simultaneously. When measured, it produces a single outcome distributed according to the resulting probabilities — never a printout of every underlying amplitude, which is exactly why "the computer tries every answer and you just read them all off" is wrong.

Multiple qubits allow a joint state with exponentially many basis possibilities. This large mathematical description does not, by itself, prove an exponential computational advantage for every task — a useful algorithm needs specific structure that makes the desired information survive interference and measurement intact. Preparing inputs, performing operations, extracting a result, and repeating when necessary all contribute to real cost. Shor and Grover exploit two genuinely different kinds of structure, which is exactly why their consequences for cryptography differ so sharply (§6, §8).

3. Reversible computation and the cost of an oracle

A quantum algorithm is commonly described using gates and oracle calls. An oracle is an operation that computes or marks a property of an input in whatever model is being analyzed — it's an abstraction for the analysis, not a magic service that already exists for free in real hardware. A cryptographic oracle may require a fully reversible implementation of a block cipher, modular arithmetic, or a verification function, and building that reversible circuit is itself real, non-trivial engineering work.

Reversible computation has to manage intermediate information explicitly. Temporary workspace can require additional qubits, and clearing it afterward may require uncomputing earlier steps rather than simply discarding them. A design can trade space against depth, or repeat work deliberately to reduce memory footprint. These tradeoffs are exactly why a count of abstract oracle queries is not directly a count of wall-clock seconds — the same query count can correspond to wildly different real runtimes depending on these engineering choices.

Error correction adds another layer of cost entirely. A long computation must maintain a sufficiently low total probability of failure across every step, not merely demonstrate one successful physical operation in isolation. A logical qubit is an error-protected computational object; its physical realization can involve many noisy physical qubits plus supporting operations. The ratio between logical and physical qubits depends on the architecture, error rates, error-correcting code, and target reliability — there is no single universal conversion constant you can apply across papers.

4. Factoring becomes order finding

RSA exposes a modulus built from large prime factors whose recovery undermines its security. Shor's factoring method connects that task to finding the period of modular exponentiation — the quantum subroutine handles the period-finding step, while ordinary classical arithmetic performs the surrounding reduction and result checking. See Shor's original paper.

Let \(N\) be the integer to factor, and choose an integer \(a\) relatively prime to \(N\). The order \(r\) of \(a\) modulo \(N\) is the smallest positive exponent satisfying \(a^r \equiv 1 \pmod{N}\). If \(r\) is even and \(a^{r/2} \not\equiv -1 \pmod{N}\), a greatest-common-divisor calculation can reveal nontrivial factors of \(N\). Some choices of \(a\) fail these conditions, which is why the algorithm includes repetition with a fresh random \(a\) when that happens.

For a tiny worked example: \(N=15\), \(a=2\) produces the residues \(2, 4, 8, 1\) — so the order is \(r=4\). Then \(a^{r/2} = a^2 = 4\), and \(\gcd(4-1, 15) = 3\) while \(\gcd(4+1, 15) = 5\). We've recovered both factors of 15. This example demonstrates the reduction, not quantum speed — anyone can enumerate four residues on paper in seconds.

The distinction between "period finding is a genuinely useful quantum primitive" and "a machine executed the full attack at cryptographic scale" matters enormously in practice. A compiled demonstration for a tiny, already-known integer can remove much of the work a general attack would actually have to perform. Its educational and research value can be entirely real without constituting any evidence of RSA-2048 being compromised — these are different claims, and headline-writing regularly conflates them.

5. Why discrete logarithms are affected too

Diffie–Hellman publishes group elements derived from secret exponents. Recovering a discrete logarithm means finding the secret exponent corresponding to a public element. The quantum approach exploits periodic structure in an appropriate algebraic formulation — the broader "hidden subgroup problem" perspective helps connect Shor's factoring and discrete-log results conceptually, but it's worth noting explicitly that not every hidden-subgroup problem automatically has an efficient known quantum solution; this is an active research area, not a solved general theory.

Finite-field DH and elliptic-curve systems use different groups, different arithmetic, and genuinely different concrete resource profiles for an attack. Both nevertheless face a structural quantum threat to their shared discrete-logarithm foundation. A smaller elliptic-curve key is not evidence of quantum safety, and an estimate built for one group should never be copied over as an estimate for another — algorithm families, parameters, and implementation costs each need separate, dedicated analysis.

For signatures, a successful recovery of the relevant secret allows future forgery. For recorded key agreement, recovering an ephemeral secret can reveal a previously-recorded session's established material — this is the mechanism behind harvest-now-decrypt-later from Part 1. These are two different effects from attacking the same underlying mathematical assumption, and whether a specific protocol transcript actually exposes enough information for this — and how the recovered value would feed into that protocol's key schedule — has to be checked at the individual protocol level, not assumed generically.

This course uses Shor's original result as the algorithmic anchor throughout. It does not infer a concrete elliptic-curve attack runtime from an RSA factoring resource paper — that would be exactly the kind of unjustified cross-paper extrapolation §9 warns against. Resource estimates are conditional constructions built around defined targets, not universal scores that apply to "classical public-key cryptography" in general.

6. Grover through four possibilities

Grover's algorithm amplifies the probability of a marked solution in an unstructured search space. Its ideal query complexity for finding one marked item among \(N\) possibilities is on the order of \(\sqrt{N}\). The algorithm alternates an operation that marks the desired state with an operation that reshapes amplitudes so the solution becomes progressively more likely to appear upon measurement. See Grover's original paper.

A four-item toy example makes the arithmetic fully visible. Start with amplitude \(1/2\) on each of four items, so each has measurement probability \(1/4\). Mark one target by flipping its amplitude to \(-1/2\). The mean amplitude across all four is now \(1/4\). Reflecting every amplitude about that mean maps the target's amplitude to \(1\) and every other item's to \(0\). In this ideal, special four-item case, measuring after exactly one iteration returns the target with certainty.

This is emphatically not a recipe for breaking a real cipher with four arithmetic operations. The oracle must be able to recognize a correct candidate against real cryptographic material, the real input space is astronomically larger than four, and the actual implementation carries the physical costs discussed in §3. The toy example explains the amplification mechanism while deliberately omitting all of that engineering reality — it also illustrates why merely creating an initial uniform superposition is not, by itself, the entire algorithm; the marking and reflection steps are doing all the real work.

For key search specifically, the oracle tests a candidate key against known input/output relationships. The complete attack has to implement that test coherently, manage all the reversible workspace from §3, and sustain the full required sequence of operations without decoherence. Extra observations may be necessary to identify a unique key when the marking condition isn't perfectly selective. A single successful match in this simplified four-item model does not establish that every real cryptanalytic task shares its clean structure.

7. Interpreting symmetric-key security responsibly

The informal expression "\(k\)-bit keys become \(k/2\)-bit secure" is a rough, ideal-query shorthand for generic Grover search — it is not an unconditional estimate of actual time, energy, or hardware cost. Parallel quantum search does not give the same simple linear scaling story that dividing classical exhaustive search into independent parallel chunks gives you; realistic circuit-depth limits can materially change the useful cost tradeoff in ways that don't reduce to a clean halved exponent.

A practical migration discussion therefore carefully distinguishes three separate statements: (1) the generic quantum algorithm exists — established mathematics; (2) a concrete, reversible implementation has an estimated cost — a model-based engineering estimate; and (3) an adversary actually has a machine capable of paying that cost — a claim that requires real evidence about real capability. Moving between these three levels without explicitly flagging which one you're discussing creates false certainty, in either direction.

NIST's PQC FAQ discusses at length why symmetric-parameter decisions shouldn't be reduced to a simplistic "quantum multiplier." It also carefully separates the urgency of replacing vulnerable public-key schemes from the continued, largely-unshaken usefulness of symmetric cryptography. The right question is always which construction, security goal, and usage limits actually apply to your case — not whether the mere word "quantum" makes all existing cryptography obsolete overnight. See the NIST PQC FAQ.

8. Why SHA-256 does not suddenly become useless

A hash can appear in very different roles: identifying an artifact, building a MAC, compressing a transcript, deriving a challenge, or contributing to a hash-based signature (Part 9). Each role calls for a specific security property. Finding any collision is not the same question as finding a preimage for one fixed target, and any security conclusion has to follow the property actually needed by the specific construction in question, not hash security in some vague general sense.

Even a generic quantum speedup does not turn a hash digest into reversible encryption — it changes the resource cost of a search problem, nothing more. A password hash can remain weak purely because its input is predictable, while a cryptographic construction using that exact same underlying hash function can have a very different, much stronger security argument. Input entropy, output length, domain separation, and the precise query model all matter independently.

For the records service, replacing a certificate's signature algorithm does not imply ripping SHA-256 out of every build manifest — that would be solving a problem that doesn't exist while ignoring the one that does. Instead, inventory exactly how hashes are used throughout the system and what actually trusts their output values. A digest cannot independently authenticate an untrusted publisher today, with or without a future quantum computer in the picture — preserving that elementary distinction from Part 2 §4 prevents a quantum-focused review from overlooking an existing, purely classical design error sitting right next to it.

9. Reading resource estimates as estimates

Gidney and Ekerå's widely-cited work estimates a construction for factoring RSA-2048 using twenty million noisy physical qubits running for roughly eight hours, under a specific set of stated physical assumptions. It models error correction and other overheads explicitly rather than naively equating logical gate counts with physical execution time. Its publication is a research result describing a possible construction, not a report that such a machine is actually operating anywhere. See Gidney and Ekerå.

Gidney's 2025 follow-up paper estimates fewer than one million noisy qubits with a runtime under a week, under a different stated set of assumptions — including a 0.1% gate error rate, a one-microsecond surface-code cycle, and a ten-microsecond control reaction time. The dramatically changed space/time tradeoff between these two papers illustrates precisely why resource estimates evolve substantially as algorithm and architecture assumptions change — it is a research trend line, not a calendar prediction pointing at a specific year. See Gidney, 2025.

Question to ask of a resource paper	Why the answer matters
What exact cryptographic target and key size?	Different groups and parameters require genuinely different arithmetic
Logical or physical qubits?	Error correction and supporting machinery change the count by orders of magnitude
Which error rates and connectivity?	Hardware assumptions determine whether the whole schedule is even feasible
Which depth, gate count, and runtime?	Space alone does not describe the full attack cost
What success probability and repetitions?	A reliable result can require more than one execution attempt
Which costs are omitted?	Control, routing, magic-state factories, and storage may matter materially
Measured, simulated, or analytically estimated?	These are three fundamentally different forms of evidence

This table is a reading aid, not a checklist that makes every estimate directly comparable to every other. Two papers may be optimizing for entirely different objectives — a smaller qubit count paired with a longer runtime is not a contradiction, it's a different point on a tradeoff curve. A responsible summary of a resource paper preserves enough of its assumptions to explain the comparison, instead of simply extracting the single most dramatic number from its abstract for a headline.

10. What a cryptographically relevant quantum computer means

The term CRQC (cryptographically relevant quantum computer) describes capability relative to a specific cryptographic target — it is not one single qubit-count threshold applicable universally to every problem. A device must support the required operations, reliability, connectivity, computation length, and control infrastructure to execute an attack at the needed scale for that specific target. Different targets (RSA-2048 vs. a particular elliptic curve, say) may cross a practical CRQC threshold at genuinely different times, possibly years apart.

The engineering response to this uncertainty does not need a precise prediction of when a CRQC will exist. It needs a defensible inventory, a realistic migration lead-time estimate, and an update process for revisiting these assumptions as new evidence arrives. If a new resource-estimate paper meaningfully changes an attack-cost estimate, a team should be able to revise its priorities accordingly — not discover, at that point, that it has no algorithm-update mechanism at all (this is exactly what Part 16 calls cryptographic agility).

11. A threat model for the records service

Asset / adversary action	Classical boundary	Quantum concern	Additional controls
Collect public-network traffic	Ephemeral classical DH/ECDH	Later recovery of recorded session material	Standardized PQ/hybrid establishment; protect endpoints
Forge an update in the future	Classical signature trust	Future private-key recovery or forgery capability	PQ signatures, trusted update channels, rollback policy
Read encrypted backups	Data key and its wrapping/storage	Depends on vulnerable public-key protection in the chain	Inventory key wrapping, retention, and access
Steal today's process memory	Endpoint isolation and key lifecycle	Does not require quantum computation at all	Patch, isolate, minimize privileges, erase secrets
Replay a valid old command	Protocol freshness checks	Not repaired by changing signature family	Authenticate context and enforce freshness

Forward secrecy against later compromise of a long-term signing key does not imply resistance to solving the original ephemeral key agreement from a stored transcript — these protect against different attacker timelines. Similarly, stronger authentication going forward does not retroactively repair old, already-captured ciphertext. These temporal distinctions need to actually appear in a written assessment, not get hidden behind a single "quantum-ready: yes/no" compliance checkbox field.

12. Worked migration scenario

Assume, purely for planning purposes, that records require twelve years of confidentiality (\(S=12\)). A gateway can be upgraded in six months, but the slowest relevant client dependency takes three years (\(M=3\)). Evaluate attack-capability horizons of five, ten, and twenty years as separate scenarios for \(Q\), deliberately without assigning any of them a probability — we're stress-testing the plan, not forecasting the future. The combined secrecy-and-migration duration for the slow path is \(S+M=15\) years.

Under the five- and ten-year \(Q\) scenarios, delaying the slow client-dependency migration leaves an obvious concern under the \(S+M>Q\) heuristic from Part 1 §5. Under the twenty-year scenario, the inequality doesn't hold for these particular inputs — but that does not prove zero risk, because the model still omits uncertainty in implementation quality, supply-chain delays, hidden dependencies, and collection reach that a real attacker might exploit. See Mosca.

Next, split the migration path explicitly. A gateway change might reduce exposure for updated clients quickly, while a legacy export channel remains fully vulnerable for years longer. Record the fraction and sensitivity of traffic still using that legacy channel — and don't call a partial deployment "complete" just because the flagship path is done. Revisit the underlying data classification too: some records may genuinely need a longer lifetime than the organizational default, and copies sitting in downstream systems may silently outlive the original retention policy that \(S\) was based on.

This exercise produces one genuinely actionable question: which dependency makes the largest, most sensitive exposure persist the longest? That's a far more useful question than asking for a single organizational "quantum readiness percentage," which tends to average away exactly the outlier dependency that matters most. Part 16 turns this same idea into concrete inventory fields, explicit ownership, milestones, and telemetry.

13. A small verification exercise

Use Python 3 to verify both the classical order-finding arithmetic from §4 and the ideal four-item Grover amplification from §6 directly. This is not quantum simulation at cryptographic scale, and it does not measure anything about a real quantum attack — it only checks that the small worked numbers in this chapter are actually correct.

from math import gcd

# Shor reduction for N=15, a=2 (Section 4)
assert [pow(2, r, 15) for r in range(1, 5)] == [2, 4, 8, 1]
assert (gcd(4 - 1, 15), gcd(4 + 1, 15)) == (3, 5)

# Ideal four-item Grover amplification (Section 6)
amplitudes = [-0.5, 0.5, 0.5, 0.5]
mean = sum(amplitudes) / len(amplitudes)
after = [2 * mean - a for a in amplitudes]
assert after == [1.0, 0.0, 0.0, 0.0]
assert sum(a * a for a in after) == 1.0

print('Toy arithmetic checks passed')

This exercise tests two claims that are small enough to reproduce exactly by hand or in a few lines of Python. It cannot validate the hardware assumptions behind a real resource paper like Gidney and Ekerå's — keeping these two very different forms of evidence clearly distinct is a core part of learning to read cryptographic research critically, rather than treating every "we verified it in Python" claim as equivalent evidence.

Why does a superposition not reveal every candidate key at once?

Measurement returns exactly one outcome, not a printout of every amplitude (§2). The algorithm has to arrange useful interference and amplification (§6) before that single measurement happens, or the outcome is just noise.

Why can a resource estimate with fewer qubits sometimes take longer to run?

Space, parallel resources, and operation depth all trade against one another (§3, §9). The specific objective and stated assumptions in a paper determine what a fair comparison even looks like — a smaller qubit count and a longer runtime is a different point on a tradeoff curve, not a contradiction.

Does replacing classical signatures protect old recorded TLS sessions?

Not by itself (§11). Recorded confidentiality depends specifically on the key-establishment and key-protection path used for those already-captured sessions — a new signature algorithm going forward does nothing to a transcript recorded yesterday.

Takeaways

• Shor and Grover threaten cryptography in structurally different ways. Shor changes the asymptotic difficulty class of factoring/discrete-log (needs a full primitive swap); Grover gives generic search a quadratic speedup (needs a parameter review, not a swap).
• "The algorithm exists," "an implementation has an estimated cost," and "an adversary has a capable machine" are three separate claims — conflating them, in either direction, creates false certainty about the actual quantum threat.
• No authoritative evidence establishes an operational CRQC today. That's a statement about current evidence, not a prediction that the situation is static.
• Resource-estimate papers need to be read with their full assumptions (qubit type, error rates, omitted costs) — extracting one headline number from an abstract routinely misrepresents the actual result.
• The \(S+M>Q\) heuristic turns an unknowable \(Q\) into an actionable question: which dependency keeps the largest sensitive exposure alive the longest, given the \(S\) and \(M\) you can actually measure today.
• A quantum threat model must stay separate from non-quantum threats (endpoint compromise, replay) that a signature-algorithm swap does nothing to fix.

References & further reading

• Shor — Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms — §4–5, the algorithmic anchor for this chapter.
• Grover — A Fast Quantum Mechanical Algorithm for Database Search — §6.
• NIST — PQC FAQ — §7, on symmetric-key parameter reasoning.
• Gidney & Ekerå — How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits — §9.
• Gidney, 2025 — updated resource estimate — §9, the revised sub-million-qubit estimate.
• NIST — PQC project overview — §10, CRQC framing.
• Mosca — the S+M>Q migration heuristic — §12, source for the worked scenario.