What a cryptographically relevant quantum computer would actually break, and how soon it might exist.
RSA encryption secures most of the public-key cryptography on the internet: HTTPS connections, SSH logins, signed software updates, encrypted email. Its security rests on the assumption that factoring a 2048-bit integer is computationally infeasible. Classical computers would need longer than the age of the universe to do it.
Shor's algorithm, published by Peter Shor in 1994, factors large integers in polynomial time on a quantum computer. For RSA-2048, the algorithm would need a few thousand logical qubits and on the order of a billion gate operations. Running on hardware that's still years away, but the algorithm itself is well understood and verified.
The algorithm reduces factoring to period finding. Pick a random number a less than N (the number you want to factor). Compute the sequence a, a², a³, ... mod N. This sequence is periodic with some period r. If r is even and a^(r/2) is not equal to -1 mod N, then gcd(a^(r/2) - 1, N) and gcd(a^(r/2) + 1, N) are non-trivial factors of N.
Finding the period r is the hard part classically. A quantum computer uses the Quantum Fourier Transform to extract the period from the amplitudes in superposition. The Fourier transform runs in polynomial time on a quantum circuit, while the best classical algorithm (general number field sieve) is sub-exponential but still exponential in practice for large numbers.
The algorithm works in theory. In practice, running it on RSA-2048 requires a fault-tolerant quantum computer with thousands of logical qubits. Current hardware has noisy physical qubits in the hundreds. The gap is engineering, not physics.
The estimates have shifted over the years as better algorithms and lower error rates have appeared. As of recent published analyses:
None of those numbers are impossible. They're well within the range of conventional engineering projects. The question is when, not whether.
The largest number factored by Shor's algorithm on a real quantum computer is small — demonstrations have used numbers with a handful of decimal digits. That's many orders of magnitude below RSA-2048, which has 617 decimal digits. The algorithms work; the hardware isn't there yet.
One reason the threat is taken seriously now: adversaries can collect encrypted traffic today and decrypt it years later when quantum hardware catches up. This is called "harvest now, decrypt later" and it's why governments and financial institutions started migrating to post-quantum cryptography years before quantum computers are ready.
If you're transmitting data that needs to stay confidential for 10+ years — medical records, state secrets, long-term contracts, certain financial instruments — the threat is already relevant. An attacker recording today's TLS traffic and decrypting it in 2035 would have your data. The fix is to use quantum-resistant algorithms before then, not after.
Symmetric encryption (AES-256) is mostly safe. Grover's algorithm gives a quadratic speedup, which can be countered by doubling the key length. AES-256 becomes effectively AES-128 under Grover — still considered secure against classical attack.
Hash functions (SHA-256, SHA-3) get the same quadratic speedup. The standard recommendation is to double the output length when using quantum-vulnerable hashes for signatures or key derivation.
Elliptic curve cryptography (ECC) is broken by Shor's variant for discrete logarithms. Any system using ECDSA, EdDSA, or DH key exchange over standard curves is vulnerable on the same timeline as RSA.