What is Shor's algorithm?
A quantum algorithm, published by Peter Shor in 1994, that factors large numbers and breaks the encryption most of the internet uses for key exchange and signatures.
Multiplying two large primes is easy. Getting them back from the product is so slow on ordinary computers that RSA encryption relies on it. Shor’s algorithm turns factoring into finding the length of a repeating pattern, then uses interference to make that length the likely measurement result.
A related version breaks elliptic-curve cryptography. Running either at a useful size needs thousands of logical qubits, far more than any machine has today. How close are quantum computers to breaking encryption?
Related
- RSAA public-key encryption method from 1977 whose security relies on how hard it is to factor the product of two large primes.
- Elliptic-curve cryptographyPublic-key cryptography based on a hard problem about points on a curve. It protects most web traffic and Bitcoin.
- Q-DayThe day a quantum computer can break the public-key encryption in wide use today, such as RSA-2048 or 256-bit elliptic curves.
- InterferenceAmplitudes adding up or cancelling when they combine. Quantum algorithms use it to make wrong answers unlikely.
- Logical qubitA reliable qubit built from many physical qubits using error correction.