What is Shor's Algorithm?
Shor's algorithm is a quantum computing method capable of factoring large numbers into their prime components and solving discrete logarithm problems in mere seconds. The security of many modern asymmetric cryptographic systems, such as RSA, the Diffie-Hellman protocol, ECDSA, and Schnorr signatures, rests on the complexity of these two mathematical challenges.
For classical computers, these problems are practically unsolvable given sufficiently long keys. The best traditional approach, the number field sieve, operates in sub-exponential time. For example, breaking an RSA-2048 key would take billions of years, whereas Shor's algorithm can accomplish this in polynomial time. This algorithm is a cornerstone of early quantum computing research, demonstrating that a sufficiently powerful quantum machine could effectively tackle problems that underpin widely used cryptographic systems.
Who Developed It and When?
Peter Shor, a mathematician at Bell Labs, introduced the algorithm in 1994. Prior to this, quantum computing existed as a theoretical discipline but lacked compelling applications for solving significant problems. Shor's work revealed that a sufficiently powerful quantum computer could break several public-key cryptographic systems, including RSA and elliptic curve cryptography, thus spurring advancements in quantum computing and the development of post-quantum cryptography resistant to such attacks.
How Does Shor's Algorithm Work?
The factorization challenge is reduced to finding the period of a particular function. Classical computers take an excessive amount of time for this search. In contrast, a quantum computer creates a superposition of many possible states and then uses interference and the quantum Fourier transform to extract the periodic structure of the function. After measurement and classical processing, the factors of the number or the solution to the discrete logarithm problem can be derived.
The operational sequence is as follows:
- Preparation (classical PC): formulates the problem and selects a random starting number.
- Quantum Core (quantum PC): identifies the hidden period of the function in one pass.
- Finalization (classical PC): utilizes the period to quickly compute the factors.
Quantum computers yield results with a certain probability. If the attempt fails, the algorithm is retried. A modified version of Shor's algorithm is used for elliptic curves, which secure the first cryptocurrency network, solving discrete logarithm problems and allowing the computation of the private key from the public key.
Why Do Quantum Computers Pose a Threat to Bitcoin?
Bitcoin transactions rely on private and public keys based on the elliptic curve secp256k1. The private key is used for signing transactions, while the public key is used for verification. Determining the private key from the public one is infeasible for classical computers, with the best algorithms requiring approximately 2¹²⁸ computational steps.
Shor's algorithm can efficiently solve the discrete logarithm problem on this curve in polynomial time, significantly reducing the time required for a successful attack. A quantum attack becomes feasible once the public key is disclosed. For certain types of outputs, the public key is revealed when the output is created, while for others, it is only disclosed upon the first spending of funds. Both ECDSA signatures and modern Schnorr signatures are vulnerable to Shor's algorithm.
However, Bitcoin mining and the SHA-256 hash function are much better protected. The Grover's algorithm offers only a quadratic speedup against them, reducing the complexity of brute-force attacks to 2¹²⁸ operations, which remains secure and can be mitigated by transitioning to longer hashes in the future.
How Many Qubits Are Needed for a Quantum Threat to Bitcoin?
It is essential to distinguish between physical and logical qubits. Physical qubits are unstable and susceptible to noise. To obtain one reliable logical qubit, dozens or even hundreds of physical qubits are needed, combined with error-correction algorithms. When researchers discuss a potential attack, they are evaluating the physical qubits of a fault-tolerant machine.
Estimates for the resources required for a quantum attack on blockchain cryptography are rapidly declining. Early theoretical studies for ion systems suggested millions of physical qubits would be necessary, but the situation has changed as of 2026:
- Google Quantum AI, in collaboration with the Ethereum Foundation and Stanford University, published a study indicating that less than 500,000 physical qubits would suffice to break a 256-bit key on a superconducting architecture. This is a reduction by a factor of 20 from previous estimates. While practical implementation is still out of reach, the theoretical threshold has been significantly lowered.
- The company IonQ unveiled the first complete engineering blueprint for attacking the secp256k1 curve. According to their calculations, the latest Walking Cat architecture would require only 19,397 physical qubits (1,457 logical qubits) for the attack, taking approximately 25.7 days to complete one key search.
The variation in numbers is attributed to the type of equipment used. IonQ's ion traps perform operations with much greater precision than Google's superconducting chips, thus requiring significantly fewer qubits for error correction. However, this comes at the cost of speed: ion machines operate much slower, resulting in nearly a month for generating a single key compared to minutes for superconductors.
What Does IonQ's Estimate Mean in Practice?
It’s important to clarify that this is a mathematical estimate, not a real-world experiment. The company has emphasized that no machine exists today that could perform such an attack—no cryptocurrency wallet or private key has been compromised.
The value of the study lies elsewhere. For the first time, Shor's algorithm has been detailed down to the minutiae, including specific error-correction gates with proven rather than presumed success probabilities. Essentially, it serves as a detailed blueprint for future devices.
To grasp the scale, the largest operational quantum processors, such as IBM's, currently contain only about 1,100-1,200 physical qubits, functioning without comprehensive error correction. The gap between one thousand noisy qubits and the required 20,000 qubits in a fault-tolerant machine remains vast.
Has Anyone Successfully Broken Keys Using Shor's Algorithm?
So far, successes have been limited to "toy" scales. In 2001, IBM's 7-qubit liquid NMR system successfully implemented Shor's algorithm for the first time, factoring the number 15. By 2012, researchers raised the benchmark to 21, but these and subsequent records were achieved through "compiled" quantum circuits that had been simplified by mathematicians prior to execution.
In the realm of elliptic curves, progress appears more dynamic, though important caveats remain. On April 24, 2026, independent researcher Giancarlo Lelli demonstrated the successful attack on a 15-bit key using a public quantum solution from IBM, earning a reward of 1 BTC from Project Eleven for this achievement. This represented a 512-fold increase in search space compared to the previous 6-bit record.
However, blockchain developers reacted with skepticism: 15 bits generate only 32,768 combinations, which a standard PC can brute-force in a fraction of a second. Moreover, due to the noise of the hardware at such scales, the results of quantum generation are barely distinguishable from random substitution.
There remains a significant distance to a real Bitcoin network key (256 bits). The gap between the 15-bit experiment and secp256k1 is enormous, but not because Shor's algorithm resources grow exponentially with each bit. The fundamental issue is the need to execute very long quantum circuits on hundreds or thousands of logical qubits with error correction. This requires orders of magnitude more robust and large-scale devices than what is available today.
Which Cryptocurrencies Are Most at Risk?
Shor's algorithm requires a public key, which is not always revealed in Bitcoin:
- P2PK format addresses (early coins, including those presumably belonging to Satoshi Nakamoto) contain the public key directly in the blockchain.
- Addresses with reuse: if a transaction has already been sent from such an address (e.g., P2PKH), the public key is revealed during the signing process. Reusing such addresses makes the balance vulnerable.
- Taproot format network (P2TR): the public key is present in the blockchain from the moment of UTXO creation. Thus, once a sufficiently powerful quantum machine emerges, these funds will be at risk even before being spent.
Addresses that have never spent funds (e.g., "clean" P2PKH, P2WPKH) conceal the key behind a cryptographic hash. They can only be attacked during a short window when a transaction is in the mempool: attackers have a few minutes to compute the key and "override" the transaction with their own. The current estimate of 26 days per key from IonQ completely rules out such an attack. Various estimates suggest that about a quarter of all existing bitcoins are currently held in addresses with exposed keys.
How Is the Industry Preparing?
In August 2024, NIST approved the first three post-quantum standards: ML-KEM for key exchange, and ML-DSA and SLH-DSA for digital signatures. In March 2025, a backup algorithm, HQC, was added, with the final standard expected by 2027.
According to NIST's draft guidance IR 8547, classical RSA and elliptic curves are set to be deemed obsolete after 2030, with a complete ban on their use in the U.S. federal sector by 2035.
In the Bitcoin community, there is active discussion around a draft proposal BIP-361, initiated by developer Jameson Lopp and a group of experts, which aims to freeze coins that are vulnerable to quantum computers.
In Ethereum, one of the key tools being considered is account abstraction, which, after the necessary protocol upgrade, would allow accounts to use various signature verification schemes, including post-quantum ones.
When Will "Q-Day" Arrive?
There is no consensus on this issue. Following the March 2026 publications, Google, Microsoft, and Cloudflare identified 2029 as a target year—not for developing a supercomputer, but for a complete transition to post-quantum encryption algorithms. Experts anticipate the emergence of a cryptographically dangerous quantum computer closer to the 2030s. However, skeptics remind us that in the 30 years since Shor's algorithm was published, only the number 21 has been factored on real hardware.
Nonetheless, research from 2026 indicates that hardware requirements are decreasing faster than expected. In just six months, the theoretical estimate for neutral atom systems has dropped from millions of qubits to 10,000-20,000.
What Should Cryptocurrency Holders Do?
- Avoid reusing addresses. Each new transaction should use a new address.
- Transfer funds from old P2PK addresses and addresses with exposed keys to new ones.
- Stay updated with wallet developments: migrating to post-quantum signatures will require user action.
- Be wary of projects that promise "quantum security" without an open code audit.
The greatest threat to the network is not a sudden hack, but chaos during a hasty migration. The sooner the community settles on a standard, the smoother the transition will be.