up:: Quantum Computing MOC

Shor vs Grover

What is the difference between Shor’s algorithm and Grover’s algorithm?

Shor’s algorithm breaks public-key cryptography completely. Grover’s algorithm halves the strength of symmetric cryptography, which a longer key fixes. One is a replacement problem and the other is a parameter change. Blurring the two is the origin of nearly every overstated claim about quantum computing and encryption, including the belief that a quantum computer breaks all encryption.

The short version:

• Shor’s solves factoring and discrete logarithms in polynomial time, which recovers a private key from its matching public key. RSA, Diffie-Hellman and every flavor of elliptic-curve cryptography fall.
• Grover’s gives a quadratic speedup on unstructured search, about √N steps where a classical search takes N. Against a symmetric cipher that halves the effective security bits.
• The fix differs completely. Shor’s requires replacing the algorithm. Grover’s requires a bigger key, and often no change at all.
• AES-128 drops to about 64 bits under Grover and AES-256 drops to about 128, which stays safe. Hash functions behave the same way.
• Neither has been run at cryptographic scale, and no CRQC exists in 2026. The resource estimates for Shor’s keep falling, which is the trend worth tracking rather than any single figure.

What is Shor’s algorithm?

Published by Peter Shor in 1994, it factors large integers and solves discrete logarithms in polynomial time, which is fast enough to break the public-key cryptography securing most of the internet.

It gives a large fault-tolerant quantum computer a practical way to recover a private key from the matching public key. That reaches RSA, Diffie-Hellman, ECDH, ECDSA, Ed25519 and Curve25519. It is the single mathematical reason the world is migrating, and it leaves symmetric encryption and hashing standing.

What is Grover’s algorithm?

Grover’s algorithm finds a target inside an unstructured space of N possibilities in roughly √N steps, where a classical brute-force search needs up to N.

That square-root speedup is called quadratic, and in cryptography it matters for one thing: brute-forcing a symmetric key or a hash preimage. An n-bit key drops to roughly n/2 bits of brute-force resistance. The response is size rather than replacement.

Shor vs Grover at a glance

Dimension	Shor’s algorithm	Grover’s algorithm
What it solves	Integer factoring and discrete logarithms	Unstructured search
Speedup class	Polynomial time, an exponential improvement over the best known classical methods	Quadratic, about √N against N
What it breaks	RSA, DH, ECDH, ECDSA, Ed25519, Curve25519	Nothing outright. It weakens rather than breaks
What it leaves standing	Symmetric ciphers and hash functions	Public-key cryptography, which is Shor’s territory
Effect on security level	Total. The private key is recoverable from the public key	Halves the effective bits. n becomes about n/2
The fix	Replace the algorithm. This is the post-quantum migration	Use a longer key. AES-256 rather than AES-128
Worked example	Breaking a 256-bit curve: 1,200 to 1,450 logical qubits (Babbush et al., 2026), down from 2,330 in the peer-reviewed 2017 estimate (Roetteler et al.)	AES-128 falls to about 64 bits; AES-256 to about 128 bits, which stays safe
Resource requirement	Thousands of error-corrected logical qubits. For RSA-2048, under 1 million noisy physical qubits (Gidney, 2025), down from 20 million in the 2021 construction (Gidney and Ekerå)	Parallelizes poorly and demands staggeringly deep circuits at cryptographic scale
Status in 2026	No machine can run it at real key sizes	No machine can run it at real key sizes

Sources: Shor’s Algorithm and Grover’s Algorithm in this Guide, each citing its primary literature. Elliptic-curve logical-qubit estimates: Babbush et al., Google Quantum AI, Ethereum Foundation and Stanford, 30 March 2026, cryptocurrency whitepaper, giving 1,200 to 1,450; and Roetteler et al., 2017, giving 2,330. Both are kept: the 2017 figure is the peer-reviewed anchor and several downstream qubit counts derive from its formula. RSA-2048 physical-qubit estimates: Gidney, 2025, arXiv:2505.15917, under 1 million noisy qubits; and Gidney and Ekerå, 2021, arXiv:1905.09749, 20 million noisy qubits in 8 hours.

How do they actually differ?

The difference is structural rather than one of degree, and it comes from what each algorithm exploits.

Shor’s exploits mathematical structure. Public-key cryptography works because certain operations are easy forward and hard backward, and that hardness rests on structured problems, factoring and discrete logarithms. Shor’s finds the structure and runs the operation backward. Once it works at scale, the key size is irrelevant, because a bigger RSA key is a bigger instance of a problem that has become easy.

Grover’s exploits nothing. A well-designed symmetric cipher has no structure to attack, so the only route is searching the key space, and Grover’s makes searching faster by a square root. A square root is a large speedup and a bounded one. Doubling the key length restores the original margin, which is why the symmetric answer is a parameter change.

That is why the migration looks the way it does. Every post-quantum standard replaces a public-key algorithm. No post-quantum standard replaces AES, because AES did not need replacing.

Where do they agree?

Both require a large fault-tolerant quantum computer that does not exist, and neither has been run against a real cryptographic key.

Both are quantum algorithms with proven speedups on paper, so the uncertainty is engineering rather than mathematics.

Both inform the same migration planning, since a full assessment covers the public-key inventory Shor’s threatens and the symmetric key sizes Grover’s argues for raising.

When does Shor’s algorithm matter?

Wherever public-key cryptography protects something with a long confidentiality horizon. Because traffic recorded today can be decrypted after a capable machine exists, Shor’s is the reason Harvest Now Decrypt Later is a present-tense concern rather than a future one.

When does Grover’s algorithm matter?

Where symmetric key sizes are small enough that halving them crosses a line. AES-128 drops to about 64 bits, which is below the threshold for long-term protection, so it is the size worth moving off. AES-256 drops to about 128, which remains out of reach.

NIST assesses even this as conservative, because Grover parallelizes poorly and the circuit depth required at cryptographic scale is extreme.

Why do people confuse them?

Because both are described as quantum algorithms that attack cryptography, and headlines rarely distinguish which cryptography.

The confusion produces a specific and common error: “quantum computers will break all encryption.” They will not. They break the public-key layer, which is roughly the part that establishes keys and proves identity, and they weaken the symmetric layer, which is the part that actually encrypts the data.

The distinction is worth stating flatly: Shor’s shatters public-key cryptography, and Grover’s merely dents symmetric cryptography.

Is one replacing the other?

Neither, and they were never alternatives. They attack different mathematics for different purposes. A complete assessment of quantum risk accounts for both, because an estate has both kinds of cryptography in it.

Common misconceptions

“Quantum computers break all encryption.” They break public-key cryptography. Symmetric encryption survives with a longer key.

“AES is broken by quantum computers.” AES-256 retains about 128 bits of effective strength under Grover, which is safe.

“Doubling my RSA key size will help.” It will not. Shor’s makes the underlying problem easy at any size, which is why the answer is replacement rather than a bigger key.

“Grover’s is half as bad as Shor’s.” They are different in kind. Grover’s halves security bits and Shor’s removes them.

“These attacks are already happening.” No machine capable of running either at cryptographic scale exists in 2026. The present-tense concern is recorded traffic rather than live decryption.

“Hashes are as exposed as public keys.” Hash functions face Grover’s, not Shor’s, so the response is a larger digest rather than a new algorithm.

Questions people ask

Does a quantum computer break AES? No. Grover’s halves the effective key strength, so AES-256 stays safe and AES-128 is the size worth moving off.

Which is more dangerous? Shor’s, by a wide margin, because its effect is total on the algorithms it reaches and no parameter change mitigates it.

Why does everyone talk about Shor’s? Because it is the one that forces a migration. Grover’s is handled by a key-size choice most organizations have already made.

How many qubits does Shor’s need? For a 256-bit elliptic curve, 1,200 to 1,450 logical qubits in the 2026 estimate and 2,330 in the peer-reviewed 2017 one. For RSA-2048, under 1 million noisy physical qubits in the 2025 optimization, down from 20 million in the 2021 construction. The trend across every published estimate is downward. See Cryptographically Relevant Quantum Computer (CRQC).

Does Grover’s threaten SHA-256? It reduces preimage resistance, and SHA-256 remains useful for most work while SHA-384 covers high-assurance use.

Is my data safe until a quantum computer exists? Data in transit today can be recorded today and decrypted later, which is why the horizon of the data matters more than the arrival date of the machine. See Harvest Now Decrypt Later.

Do the post-quantum standards address both? The standards replace public-key algorithms, which is Shor’s territory. The Grover response is a key-size decision rather than a new standard.

Which one broke in the news recently? Neither has been run at cryptographic scale. Claims of a break usually describe a small-instance demonstration or a different algorithm entirely. See Did AI just break post-quantum encryption.

---

Last verified 2026-08-10 · Maintained by Addie LaMarr, LaMarr Labs. Work with Addie at lamarrlabs.com.