Appendix D: Solutions for Chapter 1

This page collects solutions and editorial notes for the exercises in Chapter 1: The quantum threat. Compute exercises have worked solutions; open-ended exercises have an editorial note describing what a strong answer addresses.

The fuller versions of these routines are in the quantum_threat package under solutions/ch01-quantum-threat. From a clone of the companion repository, pytest tests/ch01 runs its suite. Appendix C has the setup.

Exercise 1

Three primitives, three different outcomes.

• X25519 key exchange. Shor applies: recovering the ephemeral scalar is an elliptic-curve discrete-log problem. An attacker who kept the recording reconstructs the shared secret, derives the traffic keys, and decrypts the captured session. This is the harvest now, decrypt later exposure, and it means the key exchange must be replaced with a post-quantum or hybrid KEM.
• ECDSA over P-256 authentication. Shor applies again, on the same ECDLP. The attacker recovers the server’s signing key from its public verification key and can then impersonate that server in future sessions, while the corresponding certificate or key remains trusted. This does not decrypt the recorded session. It is a forward-looking impersonation threat, and it means the signature scheme must be replaced.
• AES-256-GCM application data. Grover applies, not Shor. Grover reduces a $2^{256}$ key search to about $2^{128}$ queries in the idealized model, and the concrete cost is higher still. $2^{128}$ is out of reach, so AES-256 can stay as it is.

Why the later signing-key break does not decrypt the session: in TLS 1.3 the Certificate message supplies the server’s certified public key and CertificateVerify proves possession of the matching private key by signing the handshake transcript. The session keys, though, are derived from the ephemeral X25519 exchange, not from the certificate key. Breaking the signing key lets an attacker forge handshakes and impersonate the server going forward; it does not touch the confidentiality of a session whose keys came from the ephemeral exchange. That confidentiality was already lost through the key exchange, in the first bullet, not through the certificate.

Exercise 2

For $n = 3233$ the function increments candidate from 2 to 53 and stops, so it performs 52 trial divisions. The expected output is 3233 = 53 x 61 (52 trial divisions).

def factor_trial_division_counted(n: int) -> tuple[int, int, int] | None:
    candidate = 2
    count = 0
    while candidate * candidate <= n:
        count += 1
        if n % candidate == 0:
            return candidate, n // candidate, count
        candidate += 1
    return None


toy_modulus = 3233
result = factor_trial_division_counted(toy_modulus)
assert result is not None
p, q, count = result
print(f"{toy_modulus} = {p} x {q} ({count} trial divisions)")
# ==> 3233 = 53 x 61 (52 trial divisions)

The loop stops at the smaller prime factor, so for $n = pq$ with prime factors $p \le q$ it performs $p - 1$ divisions, not $\lfloor \sqrt{n} \rfloor$. The $3233$ case shows this directly: $53 - 1 = 52$, while $\lfloor \sqrt{3233} \rfloor = 56$. For a balanced RSA-2048 modulus the two factors are each about $\sqrt{n} \approx 2^{1024}$, so the worst-case work is about $2^{1024} \approx 1.8 \times 10^{308}$ divisions.

That is why implementation speed is beside the point. The chapter’s estimate is roughly $5.7 \times 10^{291}$ years for a single core at $10^9$ divisions per second. Speeding the implementation up by forty orders of magnitude leaves about $5.7 \times 10^{251}$ years, still vastly longer than the $1.4 \times 10^{10}$-year age of the universe. The gap is in the exponent, and no constant factor closes it.

Optional power-of-ten check: at one division per nanosecond, $1.8 \times 10^{308}$ divisions take $1.8 \times 10^{308}$ ns. Dividing by the age of the universe in nanoseconds, about $4 \times 10^{26}$ ns, gives $4.5 \times 10^{281}$, which rounds to $10^{282}$. A trial-division attack on RSA-2048 would still be running after every nanosecond since the Big Bang had elapsed $10^{282}$ times over.

Exercise 3

Editorial note. The system is the reader’s, so there is no canonical answer, but a strong one has a definite shape.

It estimates $X$, the years the data must stay protected, from the data class itself: a firmware key trusted for a device’s service life, an archive that must verify for decades. It estimates $Y$, the migration time, from the organization’s own inventory and change process. It then draws two values for $Z$, the years until a CRQC arrives, one early and one late, from a probabilistic forecast rather than from a policy deadline. The Global Risk Institute’s expert survey (Mosca & Piani, 2026), for instance, frames a cryptographically relevant quantum computer as quite possible (28—49%) within ten years and likely (51—70%) within fifteen. Those are planning horizons, not guarantees.

A worked instance: take $X = 10$ years of required protection and $Y = 5$ years to migrate, so $X + Y = 15$. Against an early $Z = 10$, $X + Y > Z$, placing the organization inside Mosca’s action window: migration must begin now. Against a late $Z = 15$, $X + Y = Z$, so there is still no schedule margin. Under either planning scenario, the decision is to begin migration immediately.

The trap the exercise guards against is treating a migration deadline as an arrival date. NCSC’s 2035 target and NSM-10’s 2035 goal are completion dates for migration, not forecasts of when a machine arrives. Using them as $Z$ confuses the policy with the prediction. State plainly which of $X$, $Y$, and $Z$ you know and which you assume: $X$ follows from the data class, $Y$ is an organizational estimate, and $Z$ is irreducibly uncertain and comes from a forecast, not a fact.

Exercise 4

Editorial note. This is a source-reading exercise, so the answer is a faithful summary, not a computation.

Gidney and Ekerå (2021) estimate RSA-2048 in about 8 hours on roughly 20 million physical qubits. Gidney (2025), by Gidney alone rather than the same pair, estimates it in under a week with fewer than one million physical qubits. Both assume the same hardware physics: a 0.1% gate-error rate under a surface code.

The point to draw out is that the twentyfold drop in qubit count is not a hardware improvement. It comes from algorithmic and error-correction changes (approximate residue arithmetic, yoked surface codes, magic-state cultivation), and it is partly a space-time tradeoff: the newer construction uses fewer qubits and runs longer, as hours become a week. Neither paper claims that physical quantum devices became twenty times better: the two estimates hold the hardware and noise assumptions fixed, so the difference is algorithmic. Physical-qubit requirements in general still depend strongly on that hardware and noise model.

References

Mosca, M., & Piani, M. (2026). Quantum Threat Timeline Report 2025. Global Risk Institute. https://globalriskinstitute.org/publication/quantum-threat-timeline-report-2025b/