The Math Problem That Protects The Entire Internet Is Dying

April 5, 2026·6 min read

Almost every encrypted message on the internet, every HTTPS connection, every signed software update, every banking session, every chat message, relies on one of two math problems being hard. The first is integer factorization. The second is the elliptic-curve discrete logarithm. Both are hard for classical computers. Neither is hard for a sufficiently large quantum computer running Shor's algorithm. That is the entire story, and it is why the cryptography community has spent the last decade scrambling to replace the foundations of internet security before anyone finishes building the machine that breaks them.

Check out the full video on my YouTube channel Divide and Quantum.

The Problem RSA Is Betting On

RSA encryption, invented by Rivest, Shamir, and Adleman in 1977, is built on one observation: multiplying two large prime numbers is easy, but factoring their product back into those primes is extraordinarily hard.

Concretely, pick two 1024-bit primes p and q. Computing n = p * q takes microseconds. Recovering p and q given only n requires, with the best known classical algorithm (the general number field sieve), roughly

exp((64/9)^(1/3) * (ln n)^(1/3) * (ln ln n)^(2/3))

operations. For a 2048-bit n, this is estimated at around 2^112 operations, well beyond what any classical computer will do in the lifetime of the universe.

The RSA public key is (n, e) where e is typically 65537. The private key is d such that e * d ≡ 1 (mod (p-1)(q-1)). You can compute d if you know p and q. You cannot compute d from (n, e) alone without factoring n.

That is the whole security argument. The fence holding up global cryptography is the belief that nobody will ever factor a 2048-bit semiprime fast.

Elliptic Curves: Same Trick, Different Math

Elliptic-curve cryptography (ECC) is what your browser actually uses for most TLS connections today. It is based on a different hard problem: given a curve, a base point G, and a point Q = kG (the point G added to itself k times using the curve's group law), recover k.

The best classical algorithms (Pollard's rho, baby-step giant-step) take roughly sqrt(n) time where n is the order of the curve's group. For the curve secp256r1 used in TLS, that is roughly 2^128 operations. Still infeasible classically.

ECC gives you the same security as RSA at much smaller key sizes, which is why it dominates modern TLS, SSH, Signal, and Bitcoin. A 256-bit ECC key is roughly as strong as a 3072-bit RSA key.

Shor's Algorithm Breaks Both

In 1994, Peter Shor published a quantum algorithm that solves integer factorization in polynomial time. More precisely, factoring an n-bit number takes O(n^3) quantum operations. The same algorithm, with minor modifications, solves the discrete logarithm problem on elliptic curves in polynomial time too.

The mechanics are worth understanding. Shor's algorithm reduces factoring to period finding: given a function f(x) = a^x mod n, find the smallest r > 0 such that f(x + r) = f(x). Once you know r, you can compute gcd(a^(r/2) - 1, n) and recover a nontrivial factor of n with high probability.

Period finding is the step that requires a quantum computer. The algorithm prepares a superposition over all inputs, applies the function, then uses the quantum Fourier transform to extract the period. Classical Fourier transforms take O(N log N) time on N inputs. The quantum Fourier transform takes O(log^2 N) gates on log N qubits, an exponential speedup that only exists because you can operate on the superposition in parallel.

The practical result: a quantum computer with a few thousand logical qubits running Shor's algorithm breaks RSA-2048 in hours. It breaks every elliptic curve standardized by NIST. It breaks Diffie-Hellman key exchange. It breaks the signatures on your software updates.

Why This Is Not Already Over

Shor's algorithm has existed for thirty years. RSA still works. Why?

Because we do not yet have a quantum computer with enough logical qubits. RSA-2048 requires roughly 4,000 logical qubits, and current estimates put the physical-qubit overhead at 1,000 to 10,000 physical qubits per logical qubit due to quantum error correction. That puts the machine needed to break RSA-2048 somewhere between 4 million and 40 million physical qubits. The largest announced systems are in the low thousands.

But the trajectory is not flat. And there is a much more immediate problem: harvest now, decrypt later. An adversary can record encrypted traffic today, store it, and decrypt it the moment a large enough quantum computer exists. Any data with a secrecy lifetime measured in decades, classified government traffic, medical records, commercial secrets, is already effectively compromised if it is being transmitted under RSA or ECC today.

This is why the transition is happening now, not when the quantum computer actually arrives.

Post-Quantum Cryptography

The response has been a decade-long international effort to standardize cryptographic algorithms that are believed to be secure against both classical and quantum attack. In 2022 and 2024, NIST finalized the first set of these standards. The three main algorithms you will see:

ML-KEM (formerly Kyber): a key encapsulation mechanism based on the module learning with errors problem over lattices. It replaces RSA and ECDH for key agreement.
ML-DSA (formerly Dilithium): a digital signature scheme, also lattice-based. It replaces RSA and ECDSA signatures.
SLH-DSA (formerly SPHINCS+): a stateless hash-based signature scheme. Slower and with larger signatures, but its security relies only on the security of hash functions, which is very well understood.

The lattice-based schemes rest on a different hard problem: given noisy linear equations over a lattice, recover the secret. No polynomial-time quantum algorithm is known for this problem, and after decades of cryptanalysis, no serious candidate has emerged.

The catch is that these algorithms have larger keys and larger ciphertexts. An ML-KEM-768 public key is about 1,184 bytes, versus 32 bytes for an X25519 key. An ML-DSA signature is about 2,420 bytes, versus 64 bytes for Ed25519. This is not a small increase when you multiply by every TLS handshake on the internet.

What This Means In Practice

Browsers have already started shipping hybrid post-quantum key exchange. Chrome and Firefox use X25519MLKEM768, which combines the classical X25519 exchange with ML-KEM-768. If either is secure, the handshake is secure. Cloudflare, Google, and AWS report that a substantial fraction of TLS 1.3 traffic now uses this hybrid.

The signature side is harder. Signatures are larger, which means larger certificates, which means slower handshakes and more bandwidth. The WebPKI is still figuring out the right path, and the migration will take years.

If you are building systems today:

Prefer TLS libraries and versions that already negotiate hybrid post-quantum key exchange.
Treat any long-term secret encrypted only with RSA or ECC as eventually compromised.
If you are designing a protocol that needs to be secure in 2040, design in post-quantum algorithms now. Retrofitting cryptographic primitives into deployed protocols is historically painful.

The Deeper Point

RSA and ECC were not broken by clever engineers finding a flaw. They were broken by a mathematical result that changes the complexity class of the underlying problem. The fence did not fall down. The ground underneath it shifted.

The lesson, more broadly, is that cryptographic security is always contingent on the current best known attacks. "Computationally infeasible" is a statement about the state of mathematics and hardware at a moment in time. The math problem that protects the entire internet has been slowly dying for thirty years, and the only reason the internet still works is that the replacement finally arrived before the attack did.

Barely.