Shor’s algorithm was introduced by mathematician Peter Shor in 1994, who then went on to publish the expanded version in 1997, and represents a principal reason organizations are now replacing vulnerable public-key cryptography.
So, it’s powerful, but it doesn't break everything, everywhere. Specifically, Shor's algorithm targets the kind of math that’s behind RSA and elliptic-curve keys. Symmetric encryption like AES and the hash functions underneath blockchains are affected far less. The algorithm can be used as a targeted weapon against public-key cryptography, and this piece walks through how it works and why it scales so much better than the best known classical methods.
What Shor's algorithm does
Shor's algorithm efficiently solves two complex math problems. The first is factoring, or breaking a large number back into the primes that were multiplied to make it. The second is the discrete logarithm, a cousin problem in different math. Classical computers slow to a crawl on both once the numbers get large, and that difficulty is the very thing keeping RSA and elliptic-curve cryptography secure. On an advanced enough quantum computer, both drop to polynomial time, which means the effort grows slowly enough to stay practical as the numbers get bigger.
Turning factoring into period-finding
The essence of Shor's algorithm is a clever workaround. Factoring a number directly is difficult, so Shor turns it into an easier question, which is finding how long a repeating pattern takes to repeat. If you build a function out of the number you want to factor, its outputs repeat on a fixed cycle. Finding that cycle length quickly is out of reach for a classical computer at the sizes cryptography uses.
A quantum computer works on many inputs together in a single quantum state, which captures the shape of that cycle. A step called the Quantum Fourier Transform (QFT) then turns that shape into a handful of measurements that point to the cycle’s length.
The machine doesn't reveal every value or hand over the answer outright. From those measurements, ordinary arithmetic works out a likely cycle length, and when it fits the right conditions, a simple shared-factor calculation gives you the factors. Runs that miss have to be repeated.
Shor swaps a hard factoring problem for an easier repeating-pattern one, then lets the quantum computer find the cycle length.
Why Shor’s algorithm is so much faster
The speedup is what it’s all about. The best-known classical factoring method runs in subexponential time, faster than brute force, but still too slow to be practical as the number grows, which is why a long RSA key is safe against ordinary computers.
Shor's algorithm runs in polynomial time, which grows far more slowly, so the quantum lead grows fast as keys get bigger. A longer key raises the classical attacker's cost severely, but does little to fend off Shor's algorithm. The quantum cost rises with key size, just far more subtly than the classical cost.
What Shor's algorithm breaks
Anything with security that relies on factoring or discrete logarithms is in danger from Shor’s algorithm. This includes RSA, along with the widely deployed finite-field and elliptic-curve systems whose security rests on discrete logarithms, among them Diffie-Hellman, ECDSA, EdDSA, Schnorr, and BLS signatures. On a blockchain, those signatures prove who can spend assets, so Shor's algorithm is the specific threat behind the quantum crypto scare. We take that mechanism apart in Can Quantum Computers Break Blockchain?.
Still, there’s plenty standing outside its reach. Shor's algorithm doesn't threaten symmetric encryption like AES or general-purpose hash functions. A different quantum algorithm, Grover's algorithm, does chip at them, though far more gently. It halves the effective strength of brute-force key and preimage searches, and has an even smaller effect on finding collisions. Therefore, AES-256 will still hold about 128 bits of security and hashes will stay safe with long enough outputs in the face of Grover’s algorithm.
The post-quantum algorithms standardized by NIST are based on problems no efficient quantum attack is known to solve, which makes them a suitable replacement, and we cover those in Post-Quantum Cryptography Explained.
Shor devastates public-key cryptography but leaves symmetric encryption and hashes standing, where Grover only chips at them.
What running it would take
Shor proved the algorithm works. Building the machine to run it against a working key is the complicated part, and no one’s managed to create such a machine yet. A full attack on RSA or an elliptic curve would require a large and capable fault-tolerant quantum computer, one that would sustain thousands of error-corrected logical qubits through a very long computation.
Depending on the hardware and error-correction method, supporting those logical qubits could take anywhere from tens of thousands to millions of physical qubits, and these are theoretical estimates with no machine yet built to match.
Today's hardware has run only small demonstrations, often circuits compiled for a specific number like 15 or 21, nowhere near a cryptographic key. Some recent estimates have fallen sharply as researchers improve circuits and codes, which we track in How Many Qubits To Break Bitcoin?.
What it means for crypto
Shor's algorithm is behind crypto's most significant quantum vulnerability, which is the recovery of a private signing key from the corresponding public key. Most major chains authorize ordinary spending with an elliptic-curve signature, which sits squarely in Shor's sights, so a blockchain has to move to a post-quantum signature before a capable machine arrives. Where each major chain stands is scored in the L1 Quantum Vulnerability Index, and we address the timing question in When Is Q-Day?.
Since migration across a decentralized network takes years, the work has to start well ahead of the threat. On programmable chains, a smart contract can require a post-quantum authorization before releasing funds, which protects that contract's assets as long as the ordinary wallet key can't bypass or remove the added check. It doesn't make the underlying chain quantum-safe.
qLABS applies this model in qVAULT, a non-custodial vault described as requiring a Falcon-based authorization before funds can be released, and which currently covers the qONE and HYPE assets. qLABS owns those products and publishes the index linked above, so weigh the product claims and the ranking with that interest in mind, and treat none of it as financial advice.
FAQ
What is Shor's algorithm in simple terms?
Shor’s algorithm is a quantum algorithm that can factor large numbers and solve discrete logarithms efficiently, two problems that are exceptionally difficult for ordinary computers. Those problems are the basis of RSA and elliptic-curve cryptography, so a quantum computer running Shor's algorithm could break them.
Does Shor's algorithm break Bitcoin?
Shor’s algorithm will threaten the ECDSA and Schnorr signatures that Bitcoin uses to authorize spending once there’s a large enough quantum computer out there. It won’t directly attack Bitcoin's SHA-256 proof of work or rewrite its block history, though recovering a signing key might let an attacker spend funds from a vulnerable output. No machine can run the attack today. You can find the details for Bitcoin in our Is Bitcoin Quantum Safe? guide.
Can Shor's algorithm run on today's quantum computers?
Not at any useful scale. Current machines have run Shor-style demonstrations only on tiny numbers, often using circuits compiled for the selected example. A working attack would require a large fault-tolerant quantum computer that nobody has built so far.
What does Shor's algorithm not break?
Quite a lot. Shor's algorithm doesn't touch symmetric encryption like AES or general-purpose hash functions, though Grover's algorithm can cut the cost of brute-force key and preimage searches, which longer keys and outputs make up for. The post-quantum algorithms that NIST standardized rely on problems no efficient quantum attack is known to solve, which is why they're the replacement.
Who invented Shor's algorithm?
The mathematician Peter Shor devised it in 1994 at Bell Labs. It was one of the first results to show a quantum computer could beat a classical one at a problem people wanted solved.
qLABS Editorial. Sources are linked inline. See the L1 Quantum Vulnerability Index for our full methodology and conflict-of-interest disclosure.
