How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits

For thirty years, the security of RSA encryption has rested on a single bet: that factoring a 2048-bit number would require so many qubits and so much time that any quantum threat remained purely theoretical. The prior estimates backed that bet. Van Meter, Jones, Fowler, and Gheorghiu — their analyses pointed toward tens of millions to a billion physical qubits. One estimate reached a billion. That gap between "Shor's algorithm exists" and "RSA is actually broken" was wide enough to feel comfortable. Then Craig Gidney and Martin Ekerå published their paper, and the gap closed by a factor of a hundred. Their result: roughly twenty million noisy physical qubits and eight hours of runtime to factor a 2048-bit RSA integer. Not millions of years. Eight hours. Not a billion qubits. Twenty million. That compression is the headline, but the more interesting story is how they got there — because it wasn't one breakthrough. It was a careful stack of smaller optimizations, each multiplying the others. Start with the algorithmic target. Shor's original algorithm requires a full two-n-bit exponent — for RSA-2048, that's a 4096-bit exponent driving the modular exponentiation. Gidney and Ekerå switch to the Ekerå–Håstad short discrete logarithm approach, which replaces that single long exponent with two shorter ones whose combined length is roughly one and a half times n rather than two times n. That alone cuts the number of quantum multiplications by about a quarter. It's not dramatic on its own. It's the foundation for everything else. On top of that come three arithmetic techniques. First, the coset representation of modular integers. Normally, adding two numbers modulo some large integer requires a modular adder — expensive, about ten Toffoli gates per bit. The coset representation lets you replace those with cheaper non-modular adders applied to periodic superpositions, dropping the cost to about four Toffoli gates per bit. That single swap cuts the dominant term in the Toffoli count roughly in half. Second, windowed arithmetic operates at two levels simultaneously. At the multiplication level, small groups of controlled additions get fused into lookup table operations — a technique using what the authors call quantum read-only memory. At the exponentiation level, groups of exponent bits get handled together per multiplication. The parameters controlling these window sizes — call them c-exp and c-mul — can be tuned, and Gidney and Ekerå find that values around five work well in practice. The effect is fewer multiplications, each requiring fewer additions, at the cost of lookup overhead that gets carefully balanced against the savings. Third, oblivious carry runways. Normal addition propagates a carry bit across the entire register — that's inherently sequential. Carry runways terminate those carries early, into short buffers, allowing additions to be done piecewise and in parallel. The approximation error this introduces is suppressed exponentially as the runway length grows. With the authors' chosen parameters, the runway approximations contribute only about 0.1 percent trace-distance error to the overall computation. Layered on all of this is the semi-classical quantum Fourier transform. Rather than maintaining full quantum superposition through the transform, exponent qubits are phased and measured iteratively, and much of the work shifts into classical post-processing. Fewer quantum resources dedicated to the transform means more room for the computation that matters. Together these techniques compound. In the abstract circuit model — which ignores the physical overhead of error correction — the construction uses approximately three times n logical qubits and zero point three times n cubed Toffoli gates. To make that concrete: three times n means roughly six thousand one hundred and forty-four logical qubits for n equals 2048. Zero point three times n cubed means about two point six billion Toffoli gates. Those are the ideal numbers. Now comes the translation to real hardware. The physical assumptions Gidney and Ekerå use are specific and plausible for large-scale superconducting platforms: a planar grid of nearest-neighbor qubits, a physical gate error rate of one in a thousand, a surface code cycle time of one microsecond, and a classical reaction time of ten microseconds. The surface code — the error-correcting scheme that encodes one reliable logical qubit in many noisy physical ones arranged on a two-dimensional grid — is their chosen protection layer. At code distance 27, a single logical qubit occupies one thousand five hundred sixty-eight physical qubits. The expensive part isn't the computation itself. It's the state preparation. Toffoli gates and T-gates can't be executed fault-tolerantly by direct means — you have to manufacture high-quality resource states through a process called magic-state distillation, where many noisy copies get distilled into a few clean ones. About twenty-five percent of the machine's logical qubit area goes to this distillation infrastructure. The distillation plan they use — level one code distance 17, level two distance 27 — contributes a total distillation error of six point four percent for the RSA-2048 workload. The runtime arithmetic is illuminating. Each lookup addition — the basic unit of the computation — has two bottlenecks. The lookup phase is limited by code depth: at distance 27 and a one-microsecond cycle, it takes about fourteen milliseconds. The addition phase is limited by reaction time: at ten microseconds reaction time, it takes about twenty-two milliseconds. Add the remaining overhead, and a single lookup addition costs roughly thirty-seven milliseconds. Multiply across the full modular exponentiation and you land at a per-run wall-clock runtime of about five point one hours. Accounting for repeated attempts — the algorithm is probabilistic — the expected spacetime volume is five point nine megaqubit-days. The physical qubit footprint to run this: twenty million. This is the hundredfold improvement over prior estimates. Now translate that to what actually breaks. RSA key exchange and RSA signatures are directly threatened — their security reduces to integer factoring. So is standard Diffie–Hellman key agreement and the Digital Signature Algorithm, both of which rely on the discrete logarithm problem in multiplicative finite fields. Gidney and Ekerå analyze both Schnorr groups and safe-prime groups — the two main families used in practice for protocols like Transport Layer Security and Internet Key Exchange, the handshaking protocols your browser and your VPN use right now — and show significant improvements across both parameterizations. Elliptic curve cryptography is a different story. Many of the arithmetic optimizations here don't translate directly to elliptic curve group operations, and the authors are careful to say so. Their tables include prior estimates for elliptic curve instances, but adapting the construction to curves remains an open research question. That distinction matters for anyone trying to triage which systems to replace first. The urgency is real and specific. Post-quantum standards are being developed, but migration of global internet infrastructure is slow and incomplete. Gidney and Ekerå state an explicit planning rule: if data must remain confidential for twenty-five years, migration away from RSA and Diffie–Hellman should happen at least twenty-five years before quantum computers capable of breaking them arrive. What makes this paper sharp is that it quantifies the arrival point. Earlier upper-end estimates sat at a billion physical qubits. This paper puts it at twenty million — a compression of nearly two orders of magnitude. That trajectory matters as much as the absolute number. None of this means RSA is broken today. The paper is explicit: current quantum machines are nowhere near the scale required. Physical assumptions will vary. And the authors list open optimizations that could shift the numbers further — improved distillation procedures, denser qubit packing, alternative multiplication routines. The engineering gap remains. But its size just changed dramatically. The value of this work is precisely its specificity: a concrete, quantitative target for engineers and policymakers to plan against, derived from physical assumptions close enough to reality to be taken seriously. Cryptographic security is a race between hardware progress and migration progress. This paper just moved the finish line significantly closer and told us exactly where it is. This lecture was created by ennepō. Go to https://ennepo.ai to Discover, Create and Follow the latest research in your field. Read when you can. Listen when you want to.