Shor's algorithm

Shor's algorithm is a quantum algorithm that factors integers and computes discrete logarithms in polynomial time. Its speedup threatens public-key cryptography based on the difficulty of those problems.

Quantum Fourier transform: A quantum operation that transforms amplitudes among computational basis states according to a discrete Fourier transform. It converts periodic structure in the algorithm's state into detectable frequency information.
RSA: A public-key cryptosystem whose security relies on the difficulty of factoring large products of primes. A sufficiently capable quantum computer could factor RSA moduli using Shor's algorithm.
Integer factorization: The problem of expressing a composite integer as a product of prime numbers. This is the best-known task Shor's algorithm solves in polynomial time.
Peter Shor: An American mathematician and computer scientist who developed the quantum factoring and discrete-logarithm algorithms. Shor published the algorithm that bears his name in 1994.
Quantum phase estimation: A quantum algorithm that estimates an eigenvalue phase by using controlled operations and quantum interference. It provides a general framework for extracting the phase that encodes a period.
Diffie–Hellman key exchange: A protocol that lets two parties establish a shared secret over a public channel using modular exponentiation. Shor's discrete-logarithm capability threatens finite-field versions of this key exchange.
Discrete logarithm: The problem of recovering an exponent from a group element raised to that exponent. Shor's algorithm solves discrete logarithms in several finite groups, beyond its factoring application.
Daniel Simon's algorithm: A quantum algorithm that identifies a hidden bit-string period with an exponential advantage over known classical methods. Its hidden-period approach helped establish techniques that Shor adapted to factoring.
Order finding: The problem of finding the least positive exponent that makes a chosen number equal to one modulo another. Shor's factoring procedure reduces integer factorization to finding a modular multiplicative order.
Elliptic-curve cryptography: Public-key cryptography based on the difficulty of discrete logarithms in groups of elliptic-curve points. Shor's algorithm also solves the underlying elliptic-curve discrete logarithm problem efficiently.

Linked from 9 pages