Lab

Shor vs Grover

Why Shor's algorithm breaks RSA but not lattices, and why Grover only forces bigger symmetric keys. Interactive period-finding and a Grover security calculator.

Two quantum algorithms, two very different threats

Shor turns factoring into period finding and destroys RSA. Grover is a generic quadratic search speedup that only weakens symmetric crypto. Lattices give Shor no period to find, which is why they anchor the post-quantum standards.

What this is

The capstone of the post-quantum story. Watch Shor read the period of ax mod N straight off a Fourier spectrum and factor N, then see the same transform find nothing in a structureless, lattice-like signal. Finally, size up Grover.

Key distinction

  • Shor: exponential → polynomial. Breaks RSA and ECC.
  • Grover: quadratic only. Halves symmetric security bits.
  • Lattices: no period, so no Shor. Grover-grade at worst.

Shor's period finding

Number to factor (N = p × q)

Period found, factors recovered. RSA at this size is broken in one shot.

The function

What the quantum Fourier transform sees

Grover's quadratic speedup

Grover finds a needle among 2n in about 2n/2 steps. It does not touch RSA's structure. It just halves the exponent of a brute-force search, so the countermeasure is a bigger key. Pick a primitive:

The whole story in four points

Shor breaks RSA and ECC

Factoring N hides a periodic structure in ax mod N. The quantum Fourier transform turns that period into sharp, evenly spaced peaks and reads it in one measurement. From the period r you recover the factors by gcd. RSA, Diffie-Hellman, and elliptic curves all fall the same way. Exponential becomes polynomial.

Grover is the smaller threat

Grover is generic search with a quadratic speedup. It cannot factor and it has no special grip on RSA. Against a symmetric cipher it turns 2n work into 2n/2, so AES-128 effectively offers 64-bit security against it. The fix is simply AES-256 and SHA-384, not a new algorithm family.

Lattices give Shor nothing

The shortest and closest vector problems have no hidden period or abelian-group structure for a Fourier transform to expose. Switch the toggle to the lattice signal and the spectrum is a flat noise floor. The best known quantum attacks are sieving algorithms with only Grover-grade speedups, which is why lattices stay hard.

So we swapped the trapdoor

The one-way function moved from integer factorization to lattice problems. Explore the new trapdoor in the Lattices and LWE labs, then the standardized schemes built on it in ML-KEM and ML-DSA.

Challenge 1: Factor 77 by hand-picking a base

Do this: Choose N = 77 and drag the base slider. Some bases show an odd period or a dead end and cannot factor.

Now: Hit "Suggest a base that works." Watch the spectrum snap to evenly spaced peaks and read off the period that splits 77 into 7 and 11.

Challenge 2: Show the lattice has no peak

Do this: Flip the toggle to "Lattices survive." The top signal turns to noise and the spectrum flattens.

Same Fourier transform that cracked RSA, applied to a structureless signal, returns nothing usable. That is the heart of why lattice cryptography is quantum-resistant.

Challenge 3: Find the AES break-even point

Do this: In the Grover panel, compare AES-128 and AES-256. AES-128 drops to a 64-bit margin; AES-256 keeps 128 bits.

This is why post-quantum guidance is "double the symmetric key size," while public-key crypto needs a whole new foundation.

Security model

Everything runs in your browser with no network calls. Period finding, the discrete Fourier transform, and the Grover estimates are plain JavaScript over small integers. This is a classical simulation of what the quantum algorithms achieve; it does not use quantum hardware, and the toy moduli are far below real RSA key sizes.