up:: Breaking Today’s Cryptography MOC

Shor’s Algorithm

Shor’s algorithm is a quantum algorithm that factors large integers and solves discrete logarithms in polynomial time, which is fast enough to break the public-key cryptography that secures most of the internet. Peter Shor published it in 1994, and it’s the single mathematical reason the world is migrating to post-quantum cryptography. It gives a large, fault-tolerant quantum computer a practical way to recover a private key from the matching public key for RSA, Diffie-Hellman, and every flavor of elliptic-curve cryptography. It does not break symmetric encryption or hashing, and no machine that can run it against real key sizes exists yet.

The short version:

• Shor’s algorithm efficiently solves two hard problems, integer factorization and the discrete logarithm problem, that classical computers can’t solve fast enough to matter. Those two problems are the entire security foundation of public-key cryptography.
• It breaks RSA, DH, ECDH, ECDSA, Ed25519, and Curve25519. It leaves symmetric ciphers like AES-256 and hash functions like SHA-256 standing, because those face a much weaker quantum attack called Grover’s algorithm, not Shor’s.
• The speed comes from period-finding. Factoring reduces to finding how often a repeating pattern repeats, and a quantum computer measures that repeat-rate across all inputs at once using the quantum Fourier transform.
• Running it against RSA-2048 or a 256-bit elliptic curve takes thousands of error-corrected logical qubits, realized today as roughly a million to twenty million noisy physical qubits. That’s a CRQC, and none exists in 2026.
• The reason to migrate before the machine arrives: harvested ciphertext (HNDL) decrypts the day a CRQC turns on, and there’s no patch for data already collected.

What does Shor’s algorithm do in plain terms?

Picture a combination lock whose combination is hidden inside a math problem. RSA hides its private key inside the problem of factoring a very large number back into the two primes that were multiplied to make it. Elliptic-curve systems hide their private key inside a discrete-logarithm problem. For a classical computer, both problems are so slow to solve at real key sizes that the answer would take longer than the age of the universe to find by brute force. That slowness is the security.

Shor’s algorithm is a procedure a quantum computer follows to solve those exact problems quickly. Feed it a public RSA key and it hands back the private key. Feed it a public elliptic-curve point and it hands back the secret scalar. The lock still looks locked, but the combination is now recoverable in hours instead of eons. Everything built on those locks, meaning key exchange, digital signatures, and the certificates behind PKI and TLS, loses its guarantee at that moment.

How does Shor’s algorithm work?

The genius of Shor’s algorithm is that it never attacks the factoring problem head-on. It converts factoring into a period-finding problem, and period-finding is the one thing a quantum computer is spectacularly good at. Here’s the shape of it, without the math:

1. Reduce factoring to finding a period. To factor a number N, pick a random number and repeatedly raise it to higher powers modulo N. That sequence eventually cycles and repeats. The length of that cycle is called the period. Number theory says that if you know the period, you can compute the factors of N with ordinary arithmetic. So the whole problem collapses down to one question: how long is the repeating cycle?
2. Compute the whole cycle at once. A classical computer would have to step through the sequence one value at a time to spot where it repeats, which is hopelessly slow. A quantum computer prepares a superposition, a state that holds every input at the same time, and evaluates the repeating function across all of them in a single pass.
3. Read the frequency with the quantum Fourier transform. The superposition now contains the repeating pattern, but you can’t just look at it, because measuring a quantum state normally gives one random answer. The Quantum Fourier Transform (QFT) is the move that saves it. It’s the quantum version of the same math that turns a sound wave into the musical notes inside it, and it converts the hidden repeat-rate into a sharp, measurable peak. Measure the state and you read out the period.
4. Finish on a classical computer. With the period in hand, a bit of ordinary post-processing recovers the factors of N, or the discrete logarithm in the elliptic-curve case.

The intuition worth keeping: factoring is secretly a question about the frequency of a repeating pattern, and quantum mechanics lets you measure that frequency directly instead of searching for it. That’s why the speedup is so dramatic. It isn’t a faster search. It’s a completely different way of asking the question.

The same period-finding machinery, pointed at a slightly different function, solves the discrete-logarithm problem too. That’s why one algorithm takes down both the factoring-based systems and the discrete-log-based ones in a single stroke.

Source: Peter W. Shor, “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer,” SIAM Journal on Computing 26(5), 1997, arXiv:quant-ph/9508027.

Which cryptography does Shor’s algorithm break?

Shor’s algorithm breaks every widely deployed public-key algorithm, because all of them rest on either factoring or a discrete logarithm, and Shor’s solves both. The breakage is total for these families, meaning the private key becomes recoverable from the public key:

Algorithm	Security rests on	What Shor’s does to it
RSA	integer factorization	Recovers the private key by factoring the modulus
Diffie-Hellman	finite-field discrete log	Recovers the shared secret
ECDH and ECDHE	elliptic-curve discrete log	Recovers the shared secret
ECDSA	elliptic-curve discrete log	Forges signatures by recovering the signing key
Ed25519 and Curve25519	elliptic-curve discrete log	Recovers the private key

Because those primitives sit underneath so much infrastructure, the reach is wide. It touches TLS and the certificates behind every HTTPS connection, PKI, VPN and IPsec key exchange, SSH, software and firmware signing, secure boot, and identity federation. The damage splits into two kinds. Where public-key crypto protects confidentiality, the risk is harvest-now-decrypt-later: an adversary records encrypted traffic today and decrypts it once a CRQC exists. Where it protects identity and trust, the risk is real-time trust failure: forged certificates, forged signatures, and impersonation the moment the machine turns on.

Why don’t AES and hashing break too?

Symmetric encryption and hashing survive because they don’t depend on factoring or discrete logs, so Shor’s algorithm has nothing to grab onto. Their security comes from having no mathematical shortcut at all. The only quantum attack against them is Grover’s algorithm, which speeds up brute-force search, and Grover’s is far weaker than Shor’s.

Grover’s gives a quadratic speedup, which effectively halves the security level. A 256-bit key drops to about 128 bits of quantum-resistant strength, and 128 bits is still comfortably out of reach for any conceivable machine. The practical fix is a longer key, and in many cases no change at all. AES-256 stays safe. SHA-256 and SHA-384 stay useful. This is the distinction people blur most often, so it’s worth stating flatly: Shor’s shatters public-key cryptography, and Grover’s merely dents symmetric cryptography.

Sources: Lov K. Grover, “A fast quantum mechanical algorithm for database search,” 1996, arXiv:quant-ph/9605043. NIST, “Report on Post-Quantum Cryptography,” NISTIR 8105, 2016, nvlpubs.nist.gov.

How many qubits does it take to break RSA-2048 or ECC P-256?

Breaking real key sizes with Shor’s algorithm takes thousands of logical (error-corrected) qubits, which today translates to somewhere between one million and twenty million noisy physical qubits, depending on the construction. The distinction between logical and physical qubits is the whole reason no CRQC exists yet: a single trustworthy logical qubit is built from hundreds to thousands of error-prone physical ones. The most-cited peer-reviewed resource estimates:

Target	Attack	Logical qubits	Physical qubits	Runtime	Source
RSA-2048	factoring	~6,100	20 million noisy	8 hours	Gidney and Ekerå, 2021
RSA-2048	factoring (optimized)	not stated	under 1 million noisy	under 1 week	Gidney, 2025
ECC P-256	discrete log	2,330	(millions after correction)	not stated	Roetteler et al., 2017

Two things stand out:

1. Elliptic-curve cryptography is an easier quantum target than RSA at comparable classical strength, because it needs fewer logical qubits. The shorter keys that make ECC efficient today are the same keys that make it fall first.
2. The physical-qubit estimate has been dropping fast as the engineering improves, from twenty million in 2019 to under a million by 2025, which is a reminder that the threshold is a moving research target rather than a fixed wall.

Sources: Craig Gidney and Martin Ekerå, “How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits,” Quantum 5, 433, 2021, arXiv:1905.09749. Craig Gidney, “How to factor 2048 bit RSA integers with less than a million noisy qubits,” 2025, arXiv:2505.15917. Martin Roetteler, Michael Naehrig, Krysta M. Svore, Kristin Lauter, “Quantum resource estimates for computing elliptic curve discrete logarithms,” 2017, arXiv:1706.06752.

Why can’t any computer run Shor’s algorithm at scale yet?

No machine can run Shor’s algorithm against real key sizes because the hardware is off by orders of magnitude on every axis that matters: qubit count, error rate, and how long the qubits stay coherent. As of 2026, the leading quantum processors have reached the low thousands of physical qubits, while breaking RSA-2048 needs on the order of a million or more of them, and those qubits have to be error-corrected into thousands of logical qubits first.

The bottleneck is error correction, not raw qubit count. Physical qubits are noisy, and Shor’s algorithm requires a very long, deep sequence of operations to run to completion. A single uncorrected error partway through corrupts the answer. Building the fault-tolerant logical qubits that can survive that depth is the hard, unsolved engineering problem, and it’s why headline qubit-count records don’t move the needle on cryptographic risk. Progress toward a CRQC is a different thing from progress in quantum computing generally. Quantum-advantage demonstrations run on problem types and qubit counts nothing like a Shor’s attack, and near-term “quantum utility” results lean on error mitigation, a statistical stopgap, rather than the error correction a CRQC demands.

The distance is now being measured directly rather than only projected forward. A 2026 study analyzed 680 order-finding distributions from IBM quantum systems and characterized exactly when classical post-processing can still recover the correct answer from a noise-distorted quantum result, which puts a hardware-reality floor beneath the timeline forecasts. Current machines are nowhere near threatening RSA-2048, and the size of that gap is now an empirical measurement.

Source: Qingxin Yang and Stefano Markidis, “When Noisy Quantum Order Finding Remains Recoverable for Shor’s Algorithm,” 2026, arXiv:2605.16074.

What does Shor’s algorithm mean for migration?

Shor’s algorithm means the migration clock started years before any machine can run the attack, because the exposure is created now and the fix takes years to deploy. Three facts drive the whole schedule:

1. Harvested data is exposed retroactively. Encrypted traffic recorded today decrypts the day a CRQC arrives. If your data has to stay confidential for a decade, its risk window opened the moment it crossed the wire. This is the logic of Mosca’s theorem: when the required secrecy lifetime plus the migration time exceeds the time until a CRQC, you are already late.
2. The replacements are standardized and available. The public-key functions Shor’s breaks have named successors. ML-KEM replaces RSA and elliptic-curve key exchange. ML-DSA and SLH-DSA replace RSA and ECDSA signatures. These rest on math problems, primarily structured lattices and hash functions, that no known quantum algorithm solves efficiently.
3. The deadline is already written down. U.S. federal policy treats the CRQC as a planning horizon rather than a surprise. NIST IR 8547 deprecates RSA and elliptic-curve cryptography by 2030 and disallows them by 2035, and CNSA 2.0 sets a parallel migration timeline for national-security systems.

The practical response to a Shor’s threat is to make systems quantum-resistant before the machine exists, using crypto-agility so algorithms can be swapped without rebuilding everything, and hybrid deployments that run a classical and a post-quantum algorithm together so security holds even if one is later found weak.

Source: NIST, “Transition to Post-Quantum Cryptography Standards,” NIST IR 8547 (initial public draft), 2024, nvlpubs.nist.gov.

Has a break on paper preceded a break in practice before?

Yes, and Shor’s algorithm is itself the current example. Shor published the algorithm in 1994, which means RSA has been broken in theory for more than thirty years while the hardware to execute the break still doesn’t exist. Cryptographic history is full of this gap between a mathematical break and a practical one, and the lesson each time is that the theory arrives first and the exploitation follows once the tooling catches up.

Cryptographic history repeats it in miniature. SHA-1 was shown weak on paper in 2005, when researchers published a collision attack far faster than brute force, yet the first real-world colliding files did not arrive until Google and CWI’s SHAttered result in 2017, twelve years later. The weakness was understood long before the capability to exploit it existed, which is exactly the position RSA and elliptic-curve cryptography are in today against Shor’s algorithm. The difference is that a quantum break is retroactive, so data harvested today is exposed the moment the hardware arrives.

Source: Stevens, Bursztein, Karpman, Albertini, Markov, “The first collision for full SHA-1,” 2017, shattered.io.

Common misconceptions

• “Quantum computers break all encryption.” They don’t. Shor’s algorithm breaks public-key cryptography specifically. Symmetric encryption (AES-256) and hashing (SHA-256) face only Grover’s algorithm, which is weak enough that a longer key handles it.
• “A qubit-count record means RSA is about to fall.” It doesn’t. The metric that matters is error-corrected logical qubits with enough circuit depth, and today’s thousands of noisy physical qubits are far below the millions needed. Raw counts on noisy machines aren’t CRQC progress.
• “RSA is stronger than elliptic-curve crypto, so it survives longer.” The opposite, against a quantum attacker. Elliptic curves need fewer logical qubits to break, so ECC P-256 is an easier target than RSA-2048 at comparable classical strength.
• “Shor’s algorithm is a faster brute-force search.” No. It doesn’t search at all. It converts factoring into period-finding and measures the period directly with the quantum Fourier transform, which is why the speedup is exponential rather than incremental.
• “There’s nothing to do until a quantum computer actually exists.” There is. Harvested data is exposed retroactively, and migration takes years, so waiting for the machine guarantees you finish too late for anything already collected.

Questions people ask

Can Shor’s algorithm break RSA today? No. The algorithm is proven and correct, but no quantum computer has anywhere near the millions of high-quality qubits and the error correction it takes to run it against a 2048-bit key. The largest genuine quantum factoring results are on tiny, specially chosen numbers that don’t threaten real keys.

Does Shor’s algorithm break AES-256? No. AES-256 is symmetric and doesn’t rely on factoring or discrete logs, so Shor’s has nothing to attack. The only quantum threat to it is Grover’s algorithm, which halves the effective strength to about 128 bits, which is still safe. This is why the post-quantum migration is overwhelmingly a public-key migration.

How many qubits does it actually take to break RSA-2048? Peer-reviewed estimates put it at roughly 6,100 logical qubits, realized as about 20 million noisy physical qubits in a 2021 construction, dropping to under a million physical qubits in a 2025 optimization (arXiv:1905.09749, arXiv:2505.15917). Every one of those has to be error-corrected, which is the hard part.

Why does breaking elliptic-curve crypto take fewer qubits than RSA? Elliptic-curve keys are much shorter than RSA keys at the same classical security level, and the quantum resource cost scales with key size. A 256-bit curve needs about 2,330 logical qubits, well under RSA-2048’s requirement, so ECC falls first against a quantum attacker (arXiv:1706.06752).

Who invented Shor’s algorithm and when? Peter Shor, then at Bell Labs, published it in 1994, with the full version appearing in SIAM Journal on Computing in 1997 (arXiv:quant-ph/9508027). It’s one of the founding results of quantum computing, because it showed a real-world problem where a quantum computer offers an exponential advantage.

What replaces the algorithms Shor’s breaks? The NIST post-quantum standards: ML-KEM for key establishment, and ML-DSA and SLH-DSA for signatures. They rest on lattice and hash-based problems with no known efficient quantum attack.

If no machine can run it, why migrate now? Because of harvest-now-decrypt-later and lead time. Data recorded today decrypts when a CRQC arrives, and a full cryptographic migration across a large estate takes years. Mosca’s theorem formalizes the math: if secrecy lifetime plus migration time is longer than the time until a CRQC, you’re already exposed.

Is Shor’s algorithm the same as Grover’s algorithm? No, and conflating them is the most common quantum-crypto error. Shor’s breaks public-key cryptography outright by solving factoring and discrete logs. Grover’s only speeds up brute-force search against symmetric ciphers and hashes, and it’s weak enough to fix with a longer key.

---

Everything here is the map, given freely. When your team needs a Shor-anchored risk picture built for your own systems and timeline, that’s the work I do. Request an alignment briefing.

Last verified 2026-07-09 · Maintained by Addie LaMarr, LaMarr Labs.