Shor's algorithm on a capable quantum computer could break RSA encryption in hours. How are governments and companies preparing for this threat?
📖 Read more: Quantum Optimization: Problems Only Quantum Can Solve
🔐 Why one algorithm terrifies governments
In 1994, mathematician Peter Shor at Bell Labs published an algorithm that could change the world. Shor's algorithm proves that a quantum computer can factorize large numbers in polynomial time — something impossible for classical computers. This means that RSA encryption, which protects banking transactions, emails, government communications and military data, will become useless the moment a sufficiently large quantum computer exists.
RSA is based on a simple principle: it's easy to multiply two large prime numbers, but extremely difficult to find which those numbers were if you only know the product. The best classical algorithm (General Number Field Sieve) requires super-exponential time. For an RSA-2048 key, that translates to billions of years. Shor's algorithm would do it in hours.
⚙️ How the algorithm works
Shor's algorithm transforms the factoring problem into a period-finding problem. If you want to find the factors of a number N, you pick a random number a and search for the period r of the function f(x) = ax mod N. Once you find the correct period, you can calculate the factors using the greatest common divisor.
What makes Shor's algorithm extraordinary is the Quantum Fourier Transform (QFT). Instead of the computer checking each possible period one by one, the QFT exploits the interference phenomenon to amplify correct answers and cancel out wrong ones. The complexity drops from super-exponential to O((log N)³) — an exponential speedup.
RSA-2048: Classical computer → billions of years. Quantum computer with Shor's algorithm → a few hours. But it requires approximately 4,000 logical qubits (or ~20 million physical qubits with today's technology).
🛡️ The “harvest now, decrypt later” principle
Perhaps the most alarming scenario concerns not the future but the present. State actors and hackers already suspect that governments are storing encrypted data today with the intent to decrypt it later, once they acquire a quantum computer capable of running Shor. This strategy — known as “harvest now, decrypt later” — makes the problem urgent even though the quantum computer doesn't exist yet.
Military secrets, diplomatic communications, medical records, trade secrets — anything that needs to remain confidential for 20+ years is already at risk. In August 2024, NIST (National Institute of Standards and Technology) published the first three post-quantum cryptography standards, initiating the largest cryptographic infrastructure upgrade in history.
"If there is even a 1% chance that a quantum computer capable of breaking RSA will be built in the next 20 years, we must act now."
— Michele Mosca, University of Waterloo🔄 Post-quantum cryptography: the answer
Post-quantum cryptography (PQC) uses mathematical problems that are believed to be hard for both classical and quantum computers. The three NIST standards are based on lattice-based cryptography, structured codes and hash-based signatures.
The CRYSTALS-Kyber algorithm (now ML-KEM) replaces Diffie-Hellman key exchange, while CRYSTALS-Dilithium (ML-DSA) and SPHINCS+ replace digital signatures. Google has already integrated ML-KEM into Chrome, Apple adopted it for iMessage, and Signal has been using hybrid post-quantum cryptography since 2023.
📊 How far are we?
The largest factorization using Shor's algorithm on quantum hardware was the number 21 (= 3 × 7) — terrifyingly small compared to RSA-2048 keys. The reason? Thousands of logical qubits are needed, while today's largest processors have only a few hundred physical qubits without full error correction.
Estimates from researchers at MIT and IBM indicate that factoring RSA-2048 would require at least 4,000 logical qubits or approximately 20 million physical qubits with today's Surface Code technology. But new techniques — cat qubits, LDPC codes, topological qubits — could dramatically reduce that number.
Year Shor's algorithm was published
Logical qubits for RSA-2048
First NIST PQC standards
⚖️ The security race of the 21st century
Shor's algorithm is not a theoretical threat — it's the driving force behind a massive shift in global security infrastructure. Governments, banks and tech companies are racing to replace their cryptographic systems before it's too late. The transition to post-quantum cryptography is not a matter of technological curiosity — it's a matter of national security.
History teaches us that transitioning from one generation of cryptography to the next takes decades. Replacing SHA-1 with SHA-256 took over 15 years. Replacing the entire public-key infrastructure is a far greater undertaking. Time is running out.