How Shor’s algorithm works
RSA is safe because multiplying two large primes is easy, but splitting the result back into those primes is not. The best classical methods would take far longer than the age of the universe for a 2048-bit key. Shor found a way around this by turning factoring into a different problem: finding the period of a repeating pattern.12
- Pick a number and build a pattern. Take a random number a and look at the remainders of a, a2, a3 and so on, divided by the number you want to factor. The remainders repeat in a cycle.
- Find the cycle length on a quantum computer. A quantum computer can work on many values at once and, using the quantum Fourier transform, read out how long the cycle is. This is the only step that needs quantum hardware.
- Finish with ordinary math. Once the cycle length is known, a classical computer turns it into the prime factors in moments.
The same trick solves discrete logarithms, the problem behind Diffie-Hellman and elliptic-curve cryptography such as X25519 and ECDSA.2
Why Shor’s algorithm matters
Almost every secure connection today starts with RSA or elliptic-curve cryptography. Shor’s algorithm means those would fall the day a large, reliable quantum computer exists, a moment called Q-Day.
That machine doesn’t exist yet. The first demonstration factored the number 15, in 2001, on a 7-qubit device.3 But estimates keep shrinking: in 2025, Craig Gidney of Google Quantum AI estimated that RSA-2048 could be factored in under a week with fewer than a million noisy qubits.4 And recorded traffic can be decrypted after the fact, which is the harvest now, decrypt later threat.
| Type | Examples | Effect |
|---|---|---|
| Public-key (classical) | RSA, Diffie-Hellman, X25519, ECDSA | Broken |
| Symmetric ciphers | AES-256 | Not affected. Grover’s algorithm gives only a square-root speedup, so 256-bit keys stay strong.5 |
| Post-quantum | ML-KEM, ML-DSA, SLH-DSA | Designed to resist it |
Where you’ll see it
- Government deadlines. NIST plans to deprecate the weaker RSA and elliptic-curve key sizes after 2030 and disallow both after 2035, because of Shor’s algorithm.6
- Quantum computing news, where new hardware is measured against how close it gets to running Shor at real key sizes.
- Post-quantum products, which replace or pair vulnerable key exchanges with ML-KEM.
How Secria handles it
Secria Mail seals every message in your mailbox with ML-KEM-1024 together with X25519, on every plan. Shor’s algorithm targets the X25519 half, but the ML-KEM-1024 half rests on lattice math with no known quantum attack, so recorded mail stays sealed. Secria VPN adds an ML-KEM-1024 protected key to every WireGuard session for the same reason.
Related terms
Sources
- Peter W. Shor, Algorithms for quantum computation: discrete logarithms and factoring, 35th IEEE Symposium on Foundations of Computer Science (1994).
- Peter W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, SIAM Journal on Computing (1997).
- Vandersypen et al., Experimental realization of Shor’s quantum factoring algorithm using nuclear magnetic resonance, Nature (2001).
- Craig Gidney, Google Quantum AI, How to factor 2048 bit RSA integers with less than a million noisy qubits (May 2025).
- Lov K. Grover, A fast quantum mechanical algorithm for database search (1996).
- NIST, IR 8547 (initial public draft): Transition to Post-Quantum Cryptography Standards (November 2024).
Checked October 2026. Secria facts are from our Mail and VPN pages and the whitepaper.
Questions about Shor’s algorithm
What is Shor’s algorithm in simple terms?
A recipe for quantum computers that finds the prime factors of huge numbers quickly. Since RSA and elliptic-curve encryption depend on that being slow, it would break them.
Has Shor’s algorithm broken RSA yet?
No. It has only been run on tiny numbers like 15. Breaking RSA-2048 is estimated to need just under a million noisy qubits, far more than any machine today.
Does Shor’s algorithm break AES?
No. Shor attacks public-key cryptography. AES is symmetric, and the best quantum attack on it, Grover’s algorithm, leaves AES-256 with ample security.
What is the difference between Shor’s and Grover’s algorithms?
Shor breaks public-key encryption outright by factoring and solving discrete logarithms. Grover speeds up brute-force searching, which only halves the effective strength of a symmetric key.