Shor

Shor refers to Peter W. Shor, an American theoretical physicist and computer scientist known for his work in quantum computation, particularly Shor's algorithm. Introduced in 1994, the algorithm demonstrates that a quantum computer can factor integers and compute discrete logarithms in time polynomial in the input size, a task that is believed to be intractable for classical computers. The factoring problem is central to many public-key cryptosystems, most notably RSA, so Shor's result has had far-reaching implications for cryptography and computer science. The algorithm does not simply speed up factoring; it rewrites the problem in a way that leverages quantum parallelism and interference through a subroutine based on the quantum Fourier transform.

The core idea is to reduce factoring to finding the period r of the modular exponentiation function a^x mod N. The quantum computer prepares a superposition over many exponents, computes a^x mod N, and applies a quantum Fourier transform to reveal the period with high probability. Once r is found, one can compute gcd(a^{r/2} ± 1, N) to obtain nontrivial factors of N, provided certain conditions hold (r even and a^{r/2} not congruent to −1 mod N). The algorithm requires a fault-tolerant quantum computer with a sufficient number of qubits and coherent quantum operations; as of now, factorization of cryptographically meaningful numbers remains theoretical.

Beyond factoring, Shor's algorithm also addresses discrete logarithms, further highlighting its significance. Its existence has catalyzed both interest in building quantum computers and the development of quantum-resistant cryptography.