Shor's Algorithm Can Factor Large Numbers Fast Enough to Break RSA and ECDSA

Peter Shor Published the Factoring Algorithm at Bell Labs in 1994

The paper appeared at the 35th Annual Symposium on Foundations of Computer Science in November 1994. Peter Shor, a thirty-five-year-old mathematician working at AT&T Bell Labs, demonstrated that a hypothetical quantum computer could factor integers in polynomial time — an exponential speedup over the best-known classical methods. RSA encryption, the backbone of internet security since 1977, depended entirely on the assumption that no machine could perform that operation efficiently.

"I realized fairly quickly that factoring was just a special case," Shor, now a professor of applied mathematics at MIT, said in a 2024 lecture at the Simons Institute. "The same quantum Fourier transform that finds the period of a modular exponentiation function also solves the discrete logarithm problem. That meant elliptic-curve cryptography was vulnerable too."

The 1994 result was theoretical. No quantum computer existed that could run the algorithm on anything beyond trivially small numbers. IBM factored the integer 15 into 3 and 5 using a seven-qubit NMR processor in 2001 — a proof-of-concept that took seven years to reach and still operated on a number any pocket calculator could handle. The gap between academic proof and practical threat remained vast, but the mathematical foundation was already locked in place.

Shor's algorithm works by reducing factoring to a period-finding problem. Given an integer N to factor, the algorithm selects a random integer a, then uses quantum superposition to evaluate the function f(x) = a^x mod N across all possible values of x simultaneously. A quantum Fourier transform extracts the period r of that function, and from r, classical arithmetic recovers the factors of N with high probability. The entire quantum portion runs in O((log N)^3) time — polynomial in the number of digits of N, compared to the sub-exponential runtime of the general number field sieve on classical hardware.

Integer Factorization on Quantum Hardware Runs in Polynomial Time

Classical factoring algorithms hit a wall that scales with key size. The general number field sieve, the fastest known classical algorithm for factoring large integers, operates in sub-exponential time: roughly exp(1.9 * (ln N)^(1/3) * (ln ln N)^(2/3)) operations. For a 2,048-bit RSA key, that translates to approximately 2^112 operations — a number so large that every supercomputer on Earth working in parallel would need billions of years to complete the task.

Shor's algorithm collapses that barrier. The quantum circuit requires roughly 2n qubits to factor an n-bit integer (where n is the number of bits in the key), and the gate complexity scales as O(n^2 * log n * log log n) with optimized arithmetic. A 2,048-bit RSA key would need a quantum computer with approximately 4,096 logical qubits — a number that sounds modest until the error-correction overhead enters the calculation.

Logical qubits are not physical qubits. Each logical qubit requires hundreds or thousands of physical qubits to implement error correction, depending on the noise characteristics of the hardware. A 2019 study by Craig Gidney and Martin Ekerå estimated that factoring a 2,048-bit RSA integer would require approximately 20 million physical qubits using surface code error correction, with a runtime of about eight hours. That estimate — widely cited for half a decade — set the benchmark for how far away the threat appeared to be.

Scott Aaronson, director of the Quantum Information Center at the University of Texas at Austin, has consistently cautioned against both complacency and panic. "Shor's algorithm is mathematically airtight," Aaronson wrote in a March 2026 blog post. "The only question has ever been when the hardware catches up. And the trend line on that question has moved in one direction for thirty years."

ECDSA Relies on the Discrete Logarithm Problem Shor Also Solves

RSA is not the only target. Shor's algorithm also solves the elliptic curve discrete logarithm problem (ECDLP) in polynomial time. ECDSA (Elliptic Curve Digital Signature Algorithm) and EdDSA (Edwards-curve Digital Signature Algorithm) both derive their security from the assumption that, given a public key Q = kG on an elliptic curve, no efficient algorithm can recover the private key k. Shor's algorithm breaks that assumption.

The attack on elliptic curves is, in some respects, more efficient than the attack on RSA. Breaking a 256-bit elliptic curve key with Shor's algorithm requires approximately 2n + 3 = 515 logical qubits — far fewer than the 4,096 logical qubits needed for a 2,048-bit RSA key. The classical security equivalence between 256-bit ECC and 3,072-bit RSA disappears entirely in the quantum setting; both fall to polynomial-time attacks, but ECC falls with a smaller quantum computer.

This distinction matters because cryptocurrency almost universally chose elliptic curves over RSA. Bitcoin uses ECDSA with the secp256k1 curve. Ethereum uses the same curve and algorithm. Solana uses Ed25519, an EdDSA scheme on Curve25519. All three chains selected elliptic-curve cryptography for its efficiency — shorter keys, faster signatures, lower bandwidth — and in doing so, chose the form of public-key cryptography that requires the fewest qubits to break.

The vulnerability is not symmetric. Only operations that expose public keys create attack surfaces. A Bitcoin address generated from a fresh key pair, used exactly once for a receive transaction and never for a send transaction, does not reveal its public key on the blockchain. The public key appears only when the owner signs an outgoing transaction. That signing event — and the window between broadcast and confirmation — is the moment a quantum attacker would need to extract the private key.

Bitcoin, Ethereum, and Solana All Depend on Curves Shor Targets

Approximately 4.6 million Bitcoin (roughly $320 billion at May 2026 prices) sit in addresses with exposed public keys, according to a January 2026 analysis by Deloitte's blockchain research division. These include pay-to-public-key (P2PK) addresses from Bitcoin's earliest years, reused pay-to-public-key-hash (P2PKH) addresses, and any address that has broadcast at least one outgoing transaction. Satoshi Nakamoto's estimated 1.1 million BTC sit almost entirely in P2PK addresses — the most vulnerable format.

Ethereum's account model exposes every externally owned account (EOA) public key after its first transaction. Unlike Bitcoin's UTXO system, Ethereum accounts are persistent; users do not generate fresh key pairs for each transaction. Every active Ethereum wallet has a publicly known ECDSA public key, making the entire network's EOA-held assets theoretically vulnerable once a sufficiently powerful quantum computer exists.

Solana's situation mirrors Ethereum's. Each Solana wallet has a single Ed25519 key pair, and the public key doubles as the wallet address. Every Solana account exposes its public key by design. The total value at risk across all three chains — plus Cardano, Polkadot, Avalanche, and dozens of smaller networks using the same signature schemes — exceeds $2.1 trillion, a figure tracked by the Cambridge Centre for Quantum Computing in its quarterly threat assessments.

John Martinis, the Nobel Prize-winning physicist and former head of Google's quantum computing hardware team, addressed the timeline question at a Stanford seminar in February 2026. "People keep asking me for a date," Martinis said. "I tell them the same thing I told Google management ten years ago: focus on the error rates, not the qubit counts. A machine with a million noisy qubits is useless for Shor's algorithm. A machine with 10,000 qubits at 10^-6 error rates changes everything."

Logical Qubit Requirements Dropped from 20 Million to Under 500,000

The Gidney-Ekerå 2019 estimate of 20 million physical qubits assumed surface code error correction with a physical error rate of 10^-3 — roughly the performance level of superconducting qubits at the time. Since then, three independent developments have compressed the resource estimates significantly.

First, Google's Willow chip (announced December 2024) demonstrated that increasing the number of physical qubits in a surface code actually reduced the logical error rate — the first time any group achieved this below-threshold operation. Willow's best reported physical error rate was approximately 3.5 * 10^-4, a threefold improvement over the 10^-3 assumption in the 2019 estimate.

Second, algorithmic optimizations published between 2021 and 2025 reduced the number of T-gates (the most expensive quantum operations) needed for modular exponentiation. A team at the University of Sydney published a windowed arithmetic optimization in 2023 that cut the T-gate count by roughly 40 percent for 256-bit elliptic curve instances.

Third — and most consequentially — a Google and Caltech team published a revised resource estimate in late March 2026 that combined improved hardware parameters with the algorithmic optimizations. Their analysis concluded that breaking Bitcoin's 256-bit ECDSA requires fewer than 500,000 physical qubits, assuming Willow-class error rates and a runtime window of approximately two hours. That figure represents a 97.5 percent reduction from the 2019 baseline. IBM and Atom Computing have both announced roadmaps targeting 100,000 physical qubits by 2030, and Google's own internal target (per its 2025 quantum roadmap) aims for one million physical qubits before 2033.

The convergence of these numbers does not mean an attack is imminent. A gap of at least 400,000 qubits separates the largest current processors (IBM's 1,386-qubit Flamingo, shipped January 2026) from the 500,000-qubit threshold. But the gap is shrinking faster than most 2019-era projections anticipated, and the slope of improvement — driven by better fabrication, lower error rates, and smarter algorithms — has not flattened.

A 15-Bit Key Fell to Quantum Hardware in April 2026

On April 7, 2026, Italian researcher Giancarlo Lelli submitted a valid solution to the QDay Prize, a 1 BTC bounty offered by Project Eleven for breaking an elliptic curve key using Shor's algorithm on real quantum hardware. Lelli's submission targeted a 15-bit key — the smallest tier in the bounty's challenge ladder — and used 26 physical qubits on an IBM Heron processor accessed through the IBM Quantum Network.

Fifteen bits is a trivially small key. Any laptop can break it in microseconds using classical brute force. The significance of Lelli's result is not in the key size but in the method: Shor's algorithm, implemented on a physical quantum processor with real gate errors, real decoherence, and real readout noise, produced the correct private key. The experiment confirmed that the theoretical algorithm translates to functioning circuits on actual hardware.

The distance from 15 bits to 256 bits is staggering. Scaling from 26 qubits to 500,000 qubits involves not just manufacturing more qubits but maintaining coherence across a system roughly 19,000 times larger. Error correction overhead grows non-linearly with circuit depth, and the modular exponentiation circuits needed for 256-bit instances are orders of magnitude deeper than those for 15-bit toy problems.

Still, the QDay Prize result landed in a context where skepticism about Shor's practicality had already been eroding for years. "Every time someone says 'but it only works on small numbers,' the definition of small gets bigger," Aaronson noted in a post the day after Lelli's result was verified. "The 15-bit demonstration is not a threat to Bitcoin today. It is a data point on a curve that has moved in one direction for three decades."

NIST finalized its first set of post-quantum cryptographic standards (FIPS 203, 204, and 205) in August 2024, selecting lattice-based and hash-based algorithms designed to resist both classical and quantum attacks. Blockchain networks have been slower to act. Ethereum's roadmap includes a "Splurge" phase with account abstraction that could enable PQC signature schemes, but no hard fork date has been set. Solana introduced an experimental Winternitz vault in late 2025 as a quantum-safe option, though adoption among validators remains minimal. Bitcoin's consensus mechanism makes protocol changes exceptionally slow; no BIP for post-quantum signatures has reached draft status.

The timeline for a cryptographically relevant quantum computer — one capable of running Shor's algorithm against 256-bit elliptic curves — remains uncertain. Estimates from credible research groups range from 2033 to 2045, with wide error bars driven by unknowns in fabrication yield, error-rate scaling, and interconnect engineering. What is not uncertain is the math. Shor's algorithm works. The hardware trajectory points toward the threshold. Migration to quantum-resistant cryptography is a question of scheduling and coordination — and for decentralized networks with no central authority to mandate upgrades, those are precisely the hardest problems to solve.