Shor's Algorithm
What is Shor's Algorithm?
Shor's AlgorithmA quantum algorithm that factors large integers and computes discrete logarithms in polynomial time, breaking RSA, Diffie-Hellman, and elliptic-curve cryptography on a sufficiently large quantum computer.
Shor's Algorithm, published by Peter Shor in 1994, solves the integer-factorization and discrete-logarithm problems in polynomial time on a fault-tolerant quantum computer. Those two problems underpin essentially every classical public-key system in production today: RSA, finite-field Diffie-Hellman, DSA, and ECDSA. While no current quantum hardware can factor cryptographically relevant key sizes, credible estimates suggest a few thousand stable logical qubits would suffice to break RSA-2048. This expectation is the root cause of the NIST PQC standardisation effort and of harvest-now-decrypt-later concerns, where adversaries record traffic today to decrypt it once Shor-capable machines exist.
● Examples
- 01
Used as the theoretical baseline for estimating quantum threat timelines against RSA-2048 and ECC P-256.
- 02
Motivates migration from classical asymmetric primitives to lattice-based KEMs such as CRYSTALS-Kyber.
● Frequently asked questions
What is Shor's Algorithm?
A quantum algorithm that factors large integers and computes discrete logarithms in polynomial time, breaking RSA, Diffie-Hellman, and elliptic-curve cryptography on a sufficiently large quantum computer. It belongs to the Cryptography category of cybersecurity.
What does Shor's Algorithm mean?
A quantum algorithm that factors large integers and computes discrete logarithms in polynomial time, breaking RSA, Diffie-Hellman, and elliptic-curve cryptography on a sufficiently large quantum computer.
How does Shor's Algorithm work?
Shor's Algorithm, published by Peter Shor in 1994, solves the integer-factorization and discrete-logarithm problems in polynomial time on a fault-tolerant quantum computer. Those two problems underpin essentially every classical public-key system in production today: RSA, finite-field Diffie-Hellman, DSA, and ECDSA. While no current quantum hardware can factor cryptographically relevant key sizes, credible estimates suggest a few thousand stable logical qubits would suffice to break RSA-2048. This expectation is the root cause of the NIST PQC standardisation effort and of harvest-now-decrypt-later concerns, where adversaries record traffic today to decrypt it once Shor-capable machines exist.
How do you defend against Shor's Algorithm?
Defences for Shor's Algorithm typically combine technical controls and operational practices, as detailed in the full definition above.
What are other names for Shor's Algorithm?
Common alternative names include: Shor factoring algorithm.
● Related terms
- cryptography№ 846
Post-Quantum Cryptography
Classical cryptographic algorithms designed to remain secure against attacks by both classical and large-scale quantum computers.
- cryptography№ 890
Quantum Cryptography
Cryptography that uses quantum-mechanical properties — typically of photons — to achieve security guarantees impossible with classical communication alone.
- cryptography№ 951
RSA Algorithm
A public-key algorithm by Rivest, Shamir and Adleman (1977) whose security rests on the difficulty of factoring the product of two large prime numbers.
- cryptography№ 454
Grover's Algorithm
A quantum search algorithm that finds a marked item in an unstructured database of N entries in roughly sqrt(N) steps, providing a quadratic speed-up against symmetric ciphers and hash functions.
- cryptography№ 732
NIST PQC Standardization
The multi-year NIST process that selects and standardizes post-quantum cryptographic algorithms; its first three standards, FIPS 203, 204, and 205, were published in August 2024.
- cryptography№ 253
CRYSTALS-Kyber
A lattice-based key-encapsulation mechanism standardized by NIST as FIPS 203 (ML-KEM) in August 2024, designed to replace RSA and Diffie-Hellman key exchange in a post-quantum world.