Shor's algorithm would let a large quantum computer factor integers and compute discrete logarithms in polynomial time, which breaks RSA, Diffie-Hellman and elliptic curve cryptography. Grover's algorithm gives only a square root speedup for searching, so it weakens symmetric keys much less. Public key systems need replacing. Symmetric ones mostly need longer keys.
What does Shor's algorithm do?
Peter Shor's 1994 paper, expanded in 1996 and posted to arXiv, gives efficient randomized algorithms for two problems: factoring integers and finding discrete logarithms. They are believed hard on classical computers, and they are the basis of several cryptosystems. The paper's algorithms take a number of steps polynomial in the input size, run on a hypothetical quantum computer.
Hard on a classical machine and easy on a quantum one is the whole threat. RSA relies on factoring. Diffie-Hellman and elliptic curve schemes rely on discrete logarithms. The same algorithm family covers all of them, which is why it affects both key exchange and digital signatures.
What does Grover's algorithm do?
Lov Grover's paper describes search through an unordered set of N items. A classical algorithm needs to look at about N/2 entries to find one with 50 percent probability. The quantum algorithm needs on the order of the square root of N steps.
Applied to a symmetric key, that turns a search over 2 to the power 128 keys into something like 2 to the power 64 quantum steps. That is a real reduction in theory. But it is a generic speedup, not a break of the cipher's structure, and it only helps with brute force.
NIST's post-quantum FAQ adds the practical side. Quantum operations are likely to be orders of magnitude slower and more energy intensive than classical ones. Attacks must usually run in parallel on large clusters, which diminishes the speedup. NIST concludes it is quite likely that variants of Grover's algorithm will provide no advantage for an attack that completes in years or even decades.
So which algorithms need replacing?
Anything built on factoring or discrete logarithms: RSA, finite field Diffie-Hellman, ECDH, ECDSA. NIST published three principal post-quantum standards in August 2024: FIPS 203 (ML-KEM, for key establishment), FIPS 204 (ML-DSA, for signatures) and FIPS 205 (SLH-DSA, a hash based signature scheme). NIST describes ML-KEM and ML-DSA as believed secure even against adversaries with a large scale quantum computer.
Symmetric algorithms and hash functions are not on the replacement list. Many organisations choose 256 bit keys where long term confidentiality matters.
When does this matter?
CISA says quantum computing capable of breaking modern public key encryption does not yet exist, and still tells government and critical infrastructure organisations to begin preparing now. NIST's transition report IR 8547 sets the planning direction, and the NIST PQC page states that NIST will deprecate and ultimately remove quantum-vulnerable algorithms from its standards by 2035, with high-risk systems moving earlier.
One reason for the urgency is harvest now, decrypt later: an adversary records encrypted traffic today and decrypts it once a machine exists. Data that must stay secret for 15 years is already in scope.
A constructed example
A software company lists where it uses public key cryptography. TLS to customers uses ECDH key exchange and RSA certificates. Its release pipeline signs binaries with ECDSA. A backup system encrypts files with AES-256 and wraps the keys with RSA.
The AES layer needs no change. The key wrapping, the TLS key exchange and the signing keys do. The team sorts them by how long the protected data must last. Backup keys wrapped with RSA come first, because those archives live for years and are easy to copy.
How to check or apply this
- Build a cryptographic inventory: algorithm, key size, library and owner for every use.
- Mark each use as public key or symmetric.
- Rank public key uses by how long the data must stay secret.
- Check which libraries and protocols you depend on already support the NIST standards.
- Plan hybrid deployments where your vendors offer them, and test performance impact.
- Keep symmetric keys at 128 bits or more, and prefer 256 for long lived data.
- Add post-quantum readiness to supplier questionnaires.
Dependency scanning can help with step one. Safeguard's SBOM and dependency scanning shows which cryptographic libraries your applications pull in, which is a starting list for the inventory.
Quick check
Does Grover's algorithm make AES-128 unsafe?
NIST's view is that it is quite likely to give no practical advantage for attacks completing in years or decades. Many organisations still choose 256 bit keys for long term data.
Is there a working quantum computer that breaks RSA today?
CISA states that quantum computing capable of breaking modern public key encryption does not yet exist.
Sources
- Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Grover, A fast quantum mechanical algorithm for database search
- NIST, Post-Quantum Cryptography project
- NIST, PQC FAQs
- NIST FIPS 203 and FIPS 204
- NIST IR 8547 (initial public draft)
- CISA, Post-Quantum Cryptography Initiative
Last reviewed: 18 October 2026.
