Overview
Curated: · Written: · Reviewed:
Shor's algorithms solve integer factorization and discrete logarithms in polynomial time on a sufficiently capable fault-tolerant quantum computer. Factoring threatens RSA; discrete logarithms threaten finite-field Diffie-Hellman, DSA, elliptic-curve Diffie-Hellman, ECDSA, and related public-key systems. They do not directly break symmetric encryption or hash functions in the same way; quantum search changes their security margins more modestly.
Factoring reduces classically to order finding. The quantum computer is used for order finding; the outer reduction and verification are classical. Choose a random a, compute gcd(a,N), and if it is one, use quantum phase estimation on reversible modular multiplication to estimate the order r where a^r equals one modulo N. Continued fractions recover an order candidate; if r is even and a^(r/2) is not plus or minus one modulo N, gcd(a^(r/2)-1,N) and gcd(a^(r/2)+1,N) yield nontrivial factors. Failed bases and samples are expected and retried; every candidate must be verified classically.
Small demonstrations often hard-code, simplify, precompute, or compile away modular arithmetic and therefore do not demonstrate cryptographically relevant factoring. Credible resource estimates must state key size, arithmetic design, logical qubits, non-Clifford gates, depth, error-correcting code and target logical error, physical qubits, cycle time, factory assumptions, and success probability. No current demo is evidence that deployed RSA keys have been factored by a cryptographically relevant quantum computer.
Migration should be risk-driven now because inventories, protocols, hardware, certificates, vendors, and long-lived data take years to replace, and harvest-now-decrypt-later exposure depends on data confidentiality lifetime. Use finalized standards such as FIPS 203 for ML-KEM and applicable sector guidance, validate interoperability and side channels, keep rollback-safe crypto agility, and do not invent algorithms or equate a hybrid construction with security automatically. The production invariant is threat-calibrated migration: algorithmic vulnerability, hardware capability, data lifetime, implementation assurance, and standards status remain separate evidence fields that drive an auditable transition plan.
The distance between a headline factoring demonstration and a cryptographically relevant machine is best held as a resource number rather than as an opinion. Published estimates for breaking RSA-2048 with the surface code have moved substantially as arithmetic and factory constructions improved: the widely cited 2019 analysis by Gidney and Ekera put it at about 20 million noisy physical qubits running for roughly 8 hours at a physical error rate near 0.1 percent, and later work by the same author reduced the qubit requirement by roughly an order of magnitude while lengthening the run. Both numbers are conditional on their stated assumptions — physical error rate, cycle time, code distance, magic-state factory design, and the modular arithmetic circuit — and quoting either without those assumptions turns an engineering estimate into a rumour. The contrast with demonstration factorings is stark: a device that factors 21 has not performed 4-bit arithmetic that scales, because most such demonstrations compile the modular exponentiation using knowledge of the answer, which removes exactly the part of the circuit that dominates the cost at 2048 bits. The practical test for any claim is to ask which of the logical qubit count, the non-Clifford gate count, the code distance and the success probability was measured and which was assumed.
Migration timing is a subtraction, not a forecast. Mosca's framing is that exposure begins when the confidentiality lifetime of data, plus the number of years the migration itself takes, exceeds the number of years until a cryptographically relevant quantum computer exists. Data with a 25-year confidentiality requirement, in an estate that needs 7 years to re-issue certificates and update embedded devices, is already exposed against any credible-machine horizon shorter than 32 years — which is the entire argument for acting now, and it holds without predicting a date. Harvest-now-decrypt-later makes the exposure concrete: traffic captured today is decrypted later, so a TLS session protecting records with a long secrecy requirement is at risk in the present tense, while an authentication signature that is verified once and never again is not. That asymmetry should drive sequencing — key establishment first, long-lived signing and firmware roots of trust next, ephemeral authentication last. The technical work is standards-bound rather than inventive: use the finalized NIST selections, which include ML-KEM for key encapsulation and ML-DSA and SLH-DSA for signatures, expect larger keys and ciphertexts to break assumptions in protocols and hardware with fixed buffers, run hybrid constructions where a classical and post-quantum secret are combined so that a flaw in either does not lose the session, and keep the ability to roll back. A migration plan that names an algorithm but cannot produce a cryptographic inventory listing where keys live and how long each protected item must stay secret has not started.
Symmetric cryptography deserves a separate and much calmer paragraph, because the common summary that quantum computers halve every key length is misleading in both directions. Grover search against a block cipher reduces the query exponent from n to n over 2, so AES-128 falls from 2 to the 128 to about 2 to the 64 oracle queries — but those queries are inherently sequential, since each Grover iteration depends on the previous one, and parallelizing across k machines only improves the count by the square root of k rather than by k. A 2 to the 64 depth circuit of reversible AES evaluations under error correction is not a near-term attack, which is why the usual guidance is to move to 256-bit symmetric keys as a margin rather than as an emergency. Hash functions behave similarly: generic collision search gains less than naive quantum arithmetic suggests once the memory access costs of the classical birthday attack are compared honestly, so SHA-256 remains a reasonable choice for collision resistance while longer digests give headroom. The practical consequence for a migration plan is prioritization, not panic. Public-key key establishment protecting long-lived confidential data is the urgent item; signatures on long-lived artifacts such as firmware and code-signing roots come next because the verification chain outlives the signature; symmetric primitives need a parameter review rather than a replacement. Stating the three separately is what turns post-quantum readiness from a slogan into a work plan someone can be assigned.