Shor's Algorithm Explained

Shor's algorithm explained in plain terms: it is a quantum computing procedure, published by mathematician Peter Shor in 1994, that can factor large integers and solve discrete logarithm problems exponentially faster than any known classical algorithm. Both capabilities are lethal to the two cryptographic primitives that secure almost every cryptocurrency wallet in existence today, RSA and elliptic-curve cryptography (ECC). This article walks through the mathematical mechanism, the hardware requirements to run it at scale, credible expert timelines, and the specific implications for Bitcoin, Ethereum, and every other blockchain that inherits these vulnerabilities.

What Shor's Algorithm Actually Does

Peter Shor published his algorithm in 1994, before practical quantum computers existed. The core insight was that a quantum computer could exploit a mathematical relationship between the problem of factoring large integers and the problem of finding the period of a function, a task quantum circuits handle with remarkable efficiency via the Quantum Fourier Transform (QFT).

The Integer Factoring Path

RSA encryption derives its security from the fact that multiplying two large prime numbers together is trivial, while reversing that operation (finding the two primes from their product) is computationally intractable for classical computers. A 2048-bit RSA key, for example, would take a classical computer longer than the age of the universe to factor using the best known algorithms (the General Number Field Sieve).

Shor's algorithm reduces that intractability to a polynomial-time problem on a quantum computer:

1. Choose a random integer *a* that is coprime to the number *N* you want to factor.
2. Use a quantum circuit to find the period *r* of the function f(x) = a^x mod N. This step uses quantum superposition and the QFT to evaluate all possible inputs simultaneously and extract the periodicity.
3. If *r* is even and a^(r/2) ≢ -1 (mod N), compute gcd(a^(r/2) ± 1, N) to obtain the prime factors.
4. Repeat with different values of *a* if needed. The expected number of repetitions is small.

The quantum speedup comes entirely from step 2. Classical period-finding is exponentially slow; quantum period-finding is polynomial. Everything else in the algorithm is classical bookkeeping.

The Discrete Logarithm Path

ECC, which underlies Bitcoin's secp256k1 curve and Ethereum's key infrastructure, relies on the discrete logarithm problem: given a public key point *Q* on an elliptic curve and the generator point *G*, find the integer *k* such that Q = kG. No efficient classical algorithm exists for this on properly chosen curves.

Shor's algorithm has a direct variant for discrete logarithms over both finite fields and elliptic curves. The structure is analogous: a quantum circuit computes a two-dimensional period of a related function, the QFT extracts it, and the private key *k* falls out. A 256-bit ECC key is generally considered roughly equivalent in classical security to a 3072-bit RSA key, yet both are broken by Shor's algorithm with a comparable number of logical qubits.

---

Why Standard Crypto Wallets Are Vulnerable

Every time you generate a Bitcoin or Ethereum address, the process involves ECC. Your private key is a 256-bit integer. Your public key is derived from it via elliptic-curve point multiplication. Your wallet address is then a hash of that public key.

The vulnerability has two layers:

• Exposed public keys. When a transaction is broadcast, the public key is revealed on-chain. A sufficiently powerful quantum computer running Shor's algorithm could derive the private key from that public key before the transaction is confirmed, allowing an attacker to redirect funds.
• Reused addresses. If an address has been used to send funds (not just receive), its public key is permanently on the blockchain. Every such address is a static target for a future quantum attacker.

Addresses that have never sent a transaction expose only the hash of a public key. Breaking a hash requires Grover's algorithm (a different quantum algorithm), which offers only a quadratic speedup rather than an exponential one, and is far less immediately threatening. Nevertheless, best practice is to assume all ECC-derived secrets will eventually be compromised.

---

Qubit Requirements: The Hardware Gap

Knowing that Shor's algorithm *can* break ECC and RSA is different from knowing when a real machine *will*. The gap is primarily one of hardware scale and error correction.

Logical vs. Physical Qubits

Current quantum computers operate with *physical* qubits, which are noisy and prone to decoherence. To run Shor's algorithm reliably, you need *logical* qubits — error-corrected qubits formed by encoding one logical qubit across many physical qubits.

Estimates for breaking a 2048-bit RSA key using leading error-correction codes (such as the surface code):

These figures are drawn from research by Banegas et al. (2021) and Craig Gidney & Martin Ekerå (2021), which revised earlier, more pessimistic estimates downward. The Gidney-Ekerå paper concluded that a 2048-bit RSA key could be broken in approximately eight hours using 20 million physical qubits running at realistic error rates.

Where Quantum Hardware Stands Today

As of 2024, the most advanced publicly announced quantum processors hold on the order of 1,000 to 1,500 physical qubits, with error rates still several orders of magnitude too high for fault-tolerant computation at scale. IBM's roadmap targets utility-scale fault-tolerant systems in the late 2020s. Google's error-correction experiments have demonstrated that below a threshold error rate, additional physical qubits genuinely suppress logical error rates, confirming the theoretical basis for scaling.

The gap between ~1,000 noisy physical qubits today and ~4 million high-fidelity physical qubits needed to break RSA-2048 is enormous. But hardware scaling in the field has been non-linear and difficult to predict.

---

Realistic Timelines: What Experts Say

There is no consensus, and any specific date carries wide uncertainty. The honest framing is a distribution of scenarios, not a single prediction.

• "Harvest now, decrypt later" (HNDL) attacks are already a concern. Nation-state adversaries can record encrypted traffic or blockchain transactions today and decrypt them once sufficient quantum hardware exists. For long-lived secrets, the clock has effectively already started.
• 2030–2035: Early risk window. Several government agencies, including the U.S. National Security Agency (NSA) and the German BSI, have issued guidance framing this decade as the window by which organisations should complete migration to post-quantum cryptography. The NSA's CNSA 2.0 suite mandates post-quantum algorithms for national security systems by 2030–2035.
• 2035–2050: Plausible cryptographically relevant quantum computer (CRQC). The Global Risk Institute's annual Quantum Threat Timeline survey of expert opinion consistently places the 50% probability of a CRQC in the 2035–2045 range. The 15% probability tail extends into the late 2020s.
• Never (for blockchain specifically). Some researchers argue that the open nature of blockchains means the community will hard-fork to post-quantum algorithms before a CRQC exists. That assumes coordinated, timely governance — an assumption cryptocurrency history does not strongly support.

The prudent framing is: the threat is not immediate, but the migration lead time is long, and the cost of being wrong is total loss of funds.

---

NIST's Post-Quantum Response

The U.S. National Institute of Standards and Technology (NIST) ran a multi-year standardisation process for post-quantum cryptographic algorithms and published its first finalised standards in August 2024:

• ML-KEM (formerly CRYSTALS-Kyber) — lattice-based key encapsulation
• ML-DSA (formerly CRYSTALS-Dilithium) — lattice-based digital signatures
• SLH-DSA (formerly SPHINCS+) — hash-based digital signatures
• FN-DSA (formerly FALCON) — lattice-based signatures, compact key sizes

These algorithms are designed to resist both classical and quantum attacks, including Shor's algorithm. Lattice-based schemes in particular have no known quantum polynomial-time attacks; the hardness problems they rely on (Learning With Errors, Short Integer Solution) are not amenable to period-finding in the way RSA and ECC are.

Migrating a blockchain protocol to any of these standards requires consensus at the protocol layer, wallet software updates, and user action to move funds to new address formats. That is a multi-year undertaking even under optimal conditions.

---

What This Means for Crypto Wallet Users

For individual holders, the practical implications are:

• Avoid address reuse. Every address whose public key is on-chain is a future target.
• Monitor protocol migration proposals. Bitcoin and Ethereum both have active research threads on quantum-resistant signature schemes. BIP-360 (QuBit) proposes a Pay-to-Quantum-Resistant-Hash address type for Bitcoin. Ethereum researchers have discussed EIP-based migrations.
• Consider the custody model. Hardware wallets and self-custody setups that use standard ECC are equally vulnerable to a CRQC as exchange-held funds. The key question is whether the custody solution can be upgraded to post-quantum algorithms.
• Evaluate new infrastructure designed for the post-quantum era. Projects built natively with NIST PQC-aligned cryptography, such as BMIC.ai's quantum-resistant wallet, do not need to retrofit defences added after the fact — the protection is architectural from the start.

The migration problem is analogous to the Y2K remediation effort: the underlying vulnerability is well-understood, the fix exists, but coordinating adoption across a fragmented ecosystem is the hard part.

---

Shor's Algorithm vs. Grover's Algorithm: A Quick Distinction

These two quantum algorithms are often conflated in media coverage, but they address different problems and pose different levels of threat to crypto.

Grover's algorithm against SHA-256 (used in Bitcoin's proof-of-work and address derivation) requires roughly 2^128 operations even with quantum acceleration, which remains computationally infeasible. SHA-256 address hashing is not the acute vulnerability. ECC key derivation is.

---

Summary: The Core Takeaways

• Shor's algorithm uses quantum period-finding via the Quantum Fourier Transform to factor integers and solve discrete logarithms in polynomial time.
• It directly breaks RSA and ECC, the cryptographic foundations of every major cryptocurrency wallet today.
• Breaking a 2048-bit RSA or 256-bit ECC key requires roughly 4 million physical qubits operating below fault-tolerance thresholds. Today's machines have roughly 1,000 to 1,500 noisy physical qubits.
• Expert consensus places the 50% probability of a cryptographically relevant quantum computer in the 2035–2045 window, with a meaningful tail risk in the late 2020s.
• NIST has finalised post-quantum standards (ML-KEM, ML-DSA, SLH-DSA, FN-DSA) that are resistant to Shor's algorithm.
• Blockchain protocol migration is technically possible but requires coordinated governance that has historically proven slow in the cryptocurrency space.
• Individual holders can reduce exposure now by avoiding address reuse and monitoring protocol-level PQC migration proposals.