How Shor's Algorithm Breaks RSA and Elliptic-Curve Encryption

In 1994 a mathematician at Bell Labs published a paper that quietly set a countdown running on the internet's security. Peter Shor showed that a sufficiently large quantum computer could factor huge numbers and compute discrete logarithms efficiently. Those two problems are the foundations of RSA and elliptic-curve cryptography, the systems that protect nearly every login, payment, software update and private message sent in the last three decades.

For most of that time Shor's algorithm was a theoretical warning. It is now an engineering target with shrinking resource estimates. This article explains, without equations, how the algorithm works, where the latest estimates stand, and why VOIDEX built its encryption around the assumption that the countdown will reach zero.

The problems Shor solves

RSA depends on integer factoring. Your public key contains a very large number that is the product of two secret primes. Anyone can use it to encrypt, but only someone who knows the primes can decrypt. Multiplying the primes takes a fraction of a second. Recovering them from a 2,048-bit product is far beyond any classical computer.

Elliptic-curve cryptography depends on the discrete logarithm problem on a curve. A private key is a secret number; the public key is a point you reach by "adding" a fixed starting point to itself that many times. Going forward is fast. Working backwards to the secret number is, classically, infeasible at 256 bits. X25519, Ed25519, the NIST P-curves and the secp256k1 curve used by Bitcoin and Ethereum all rely on it.

Shor's insight was that both problems can be rewritten as the same kind of question: find the period of a repeating pattern.

Period finding, in plain English

Take a number you want to factor, call it N, and pick a random number smaller than it. Now compute successive powers of that random number, each time keeping only the remainder after dividing by N. The sequence of remainders eventually repeats. The length of that cycle is called the period.

Here is the useful part: once you know the period, a few lines of classical arithmetic usually reveal a factor of N. Finding the period is the only hard step. For a 2,048-bit N the cycle can be astronomically long, far too long to walk through one step at a time.

A quantum computer does not walk through it. It prepares a register in superposition over many exponents at once, computes the remainders for all of them in a single reversible operation, and then applies the quantum Fourier transform. The Fourier transform is the same mathematical tool engineers use to find the dominant frequency in a sound. Applied here, interference makes the amplitudes of wrong answers cancel and pushes the measurement toward values that reveal the period. A little classical post-processing recovers it, and the factor follows.

The discrete logarithm version works on the same principle. The pattern is different, but it is still a hidden periodic structure, and the quantum Fourier transform exposes it. That is why elliptic curves fall to Shor just as RSA does.

Why it has not happened yet

If the algorithm is thirty years old, why is RSA still standing? Because running Shor at useful sizes needs a large, error-corrected quantum computer. Real qubits are noisy, and a factoring run involves billions of operations. Each logical qubit the algorithm uses has to be built from many physical qubits running constant error correction.

Honest demonstrations of Shor's algorithm on real hardware have only factored very small numbers, such as 15 and 21. That gap between toy examples and RSA-2048 is enormous. It is also closing from both ends: hardware is improving, and algorithms are getting cheaper.

The estimates are falling

The number that matters is how many physical qubits, running for how long, it would take to break a real key. Those estimates have dropped sharply.

• 2019: Craig Gidney and Martin Ekerå estimated about 20 million noisy qubits running for roughly eight hours to factor RSA-2048.
• May 2025: Gidney, at Google Quantum AI, revised that to fewer than one million noisy qubits running for under a week, using better arithmetic and more compact storage of error-corrected data.
• February 2026: Iceberg Quantum's "Pinnacle" architecture used QLDPC error-correcting codes in a simulated design estimated at under 100,000 physical qubits for RSA-2048. It is a simulation, not hardware.
• March 2026: Google Quantum AI reported that 256-bit elliptic-curve discrete logarithms, the kind protecting Bitcoin and Ethereum signatures, could be solved with fewer than 500,000 physical qubits in minutes of runtime. The team withheld the circuits and published a zero-knowledge proof that the result holds.

All three recent results are summarised by The Quantum Insider. None of them is a working attack. Together they show the direction: each year the machine required looks smaller.

There is a detail in these numbers worth noticing. Elliptic curves use much shorter keys than RSA for the same classical strength, and that makes them a smaller target for a quantum computer. A 256-bit curve needs fewer logical qubits to attack than a 2,048-bit RSA modulus. The efficiency that made elliptic curves popular also makes them the first to fall.

What does not break

Shor's algorithm is devastating, but narrow. It targets problems with hidden periodic structure. It does not help against:

• Symmetric ciphers such as AES, which have no such structure. The relevant quantum attack there is Grover's algorithm, which only offers a square-root speedup. We explain why AES-256 survives in Grover's algorithm and AES-256.
• Hash functions such as SHA-256, for the same reason.
• Lattice-based cryptography, such as ML-KEM and ML-DSA. No efficient quantum algorithm is known for the lattice problems they rely on, which is why NIST chose them.

On 13 August 2024, NIST published FIPS 203 (ML-KEM), FIPS 204 (ML-DSA) and FIPS 205 (SLH-DSA) as its first post-quantum standards. Its draft transition report, IR 8547, proposes deprecating quantum-vulnerable RSA and elliptic-curve algorithms after 2030 and disallowing them after 2035.

Two different kinds of damage

Shor's algorithm hurts in two ways, and they call for different urgency.

Broken key exchange is retroactive. If an attacker recorded a conversation whose key was agreed with RSA or elliptic curves, a future quantum computer can recover that key and read everything. This is the harvest now, decrypt later problem, and it means key exchange has to be quantum-safe today.

Broken signatures are forward-looking. A signature proves who sent something at the moment it is checked. A quantum attacker cannot go back and fake a signature on a message you already verified, but once signatures are breakable they can impersonate people and services from then on. Signatures need to migrate before that day, and systems need a way to spot a forged key.

How VOIDEX answers Shor

VOIDEX treats both kinds of damage as current design requirements.

Key agreement. Every direct conversation in VOIDEX Messenger begins with a PQXDH-style handshake that combines X25519 with ML-KEM-768. The shared key depends on both. Shor's algorithm can, in principle, break the X25519 half; it has no known way through the ML-KEM-768 half. We explain the combination in Why hybrid post-quantum encryption wins.

Continuous re-keying. A double ratchet with post-quantum re-keying gives every message its own key, providing forward secrecy and post-compromise security.

Signatures. Device identities are signed with hybrid Ed25519 plus ML-DSA-65, so proving who you are talking to does not rest on elliptic curves alone.

Detecting a forged key. Every device key change is appended to a public, append-only Merkle log in the style of Certificate Transparency, with tree heads signed by Ed25519 plus ML-DSA-65. VOIDEX clients check keys against the log and refuse keys that are not in it, public endpoints let anyone audit it, and an independent witness watches it. A quietly substituted key would have to appear in public. More in Key transparency.

Groups and private VOIDEX Channels use MLS, RFC 9420. Keys are generated on members' devices and VOIDEX servers hold only public keys and ciphertext. The cryptographic core is open source and documented in the public security report.

The takeaway

Shor's algorithm is not a vague threat. It is a specific, well-understood procedure that turns the hard problems behind RSA and elliptic curves into a frequency-finding exercise a quantum computer is built for. The only open question is when the hardware catches up, and the answer keeps moving closer. The responsible move is to stop relying on those problems alone before that date, not after.

VOIDEX is invite-only. Request access to join, or explore the design behind VOIDEX encryption.

Sources

• Shor, P. "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer" (1994, arXiv version 1995): https://arxiv.org/abs/quant-ph/9508027
• Gidney, C. and Ekerå, M. "How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits" (2019): https://arxiv.org/abs/1905.09749
• Gidney, C. "How to factor 2048 bit RSA integers with less than a million noisy qubits" (2025): https://arxiv.org/abs/2505.15917
• The Quantum Insider, "Q-Day just got closer" (31 March 2026): https://thequantuminsider.com/2026/03/31/q-day-just-got-closer-three-papers-in-three-months-are-rewriting-the-quantum-threat-timeline/
• NIST Post-Quantum Cryptography Standardization: https://csrc.nist.gov/projects/post-quantum-cryptography/post-quantum-cryptography-standardization
• NIST IR 8547 (initial public draft, November 2024): https://nvlpubs.nist.gov/nistpubs/ir/2024/NIST.IR.8547.ipd.pdf
• RFC 9420, The Messaging Layer Security Protocol: https://www.rfc-editor.org/rfc/rfc9420