The Shor algorithm is one of the best-known [[Quantum Algorithm|quantum algorithms]] for [[Fault-Tolerant Quantum Computer|fault-tolerant quantum computers]]. Developed by the computer scientist Peter Shor in 1994, it demonstrated for the first time that a quantum computer could solve certain problems exponentially faster than any known classical [[Algorithm|algorithm]]. At its core, Shor's algorithm provides an efficient way to factor large integers. This makes it possible to factor numbers efficiently, **meaning to break them down into smaller prime numbers that multiply to the original value**. On classical computers, integer factorization is computationally hard; the best-known algorithms take superpolynomial time, **which means the time required grows faster than any polynomial as the numbers get larger, making it impractical for very large inputs**. In contrast, Shor's algorithm can factor large numbers much faster—using only a reasonable amount of time even as the numbers get bigger—by taking advantage of quantum computing. **The algorithm has two main steps: reduce factoring to finding the period of a function (done classically), then use a quantum computer to find that period efficiently.** Quantum computers can find the period exponentially faster than classical ones, which is where the speed-up comes from. This breakthrough has significant implications for cryptography. Many modern encryption systems, most notably the [[Rivest-Shamir-Adleman Algorithm|RSA]] algorithm, rely on the difficulty of factoring large integers as a cornerstone of their security. A sufficiently powerful quantum computer running Shor's algorithm could break RSA (by efficiently finding the private key from the public key). While current quantum hardware is not capable of factoring large RSA-sized numbers, experimental implementations of Shor’s algorithm have been demonstrated for small integers (e.g., 15, 21) on existing quantum devices. These early tests validate the algorithm’s core principles and guide the ongoing development of quantum architectures. >[!read]- Further Reading >- [[Encryption]] >- [[Rivest-Shamir-Adleman Algorithm|RSA]] >- [[Quantum Computer]] >[!ref]- References >- P. W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, SIAM Rev. **41**, 303 (1999).