Shor's algorithm
- algorithms
Peter Shor presented a quantum algorithm in 1994 that could factor integers efficiently on a suitable quantum computer. The approach connects factoring to finding a mathematical period and uses quantum computation to obtain information about that period. Its significance for cryptography is conditional: a sufficiently capable, error-corrected implementation would threaten systems whose security depends on related number-theoretic difficulty, including RSA. The publication itself did not supply such a machine or demonstrate the breaking of practical keys. It changed the theoretical relationship between quantum computing and an important classical computational problem. **Timeline anchor:** 1 January 1994 CE. **References:** [Source 1](https://en.wikipedia.org/wiki/Shor%27s_algorithm).
Sources
Related
On other timelines
- Shor presents quantum algorithms for factoring and discrete logarithms on Evolution of computer architecture · CPUs, parallel systems and alternative machines by @athan