← Quantum Store · Guides · Lessons · Glossary · About · Türkçe
What is Shor’s algorithm?
Shor’s algorithm factors large numbers exponentially faster than known classical methods, which is why it threatens RSA encryption.
Found by Peter Shor in 1994, the algorithm turns factoring into a period-finding problem and finds the period with the quantum Fourier transform. The best known classical algorithms take close to exponential time; Shor takes polynomial time.
Today’s quantum computers have only factored small numbers such as 15 and 21; breaking RSA-2048 is estimated to need millions of physical qubits and error correction. Still, the threat led to the development of quantum-resistant (post-quantum) encryption standards.
Related packages
Related concepts
- Quantum Fourier transform (QFT) · The quantum Fourier transform (QFT) computes the discrete Fourier transform of the amplitudes with H and controlled-phase gates; it underlies period finding and phase estimation.
- Quantum phase estimation (QPE) · Quantum phase estimation (QPE) reads the phase a gate adds to one of its eigenstates as a binary number in counting qubits, using phase kickback and the inverse Fourier transform.
- Post-quantum cryptography (PQC) · Post-quantum cryptography means encryption algorithms that run on today’s classical computers and are believed to stay secure against large quantum computers.
- Grover’s algorithm · Grover’s algorithm finds a marked item among N unsorted items in about √N steps, a quadratic speed-up over classical search.