edVirtus Reference

What Is Shor's Algorithm?

How Could Shor's Algorithm Affect Modern Cryptography?

Shor's algorithm is a quantum computing algorithm developed by mathematician Peter Shor in 1994 for efficiently factoring large integers and solving the discrete logarithm problem. These mathematical problems form the security foundation of many widely used public-key cryptographic systems, including RSA, Diffie–Hellman, and Elliptic Curve Cryptography (ECC). If sufficiently powerful quantum computers become available, Shor's algorithm could render many of these systems insecure.

The basic principle is straightforward. Modern public-key cryptography relies on mathematical problems that are easy to perform in one direction but extremely difficult to reverse using conventional computers. For example, multiplying two very large prime numbers is straightforward, but determining those original primes from their product may require an impractically long time using classical algorithms. Shor's algorithm exploits the unique properties of quantum computation to solve these problems far more efficiently than any known classical method.

A useful analogy is searching for a single book in a vast library. A conventional computer examines the shelves one after another until the correct book is found. A sufficiently capable quantum computer running Shor's algorithm could exploit quantum mechanical principles to identify the correct shelf much more efficiently, dramatically reducing the search time.

The algorithm has profound implications for cybersecurity because many secure communication protocols rely upon public-key cryptography. Digital certificates, secure web browsing using Transport Layer Security (TLS), Virtual Private Networks (VPNs), secure email, software signing, and many authentication systems depend upon algorithms such as RSA or ECC. If these algorithms became vulnerable, many existing security infrastructures would require replacement.

Fortunately, Shor's algorithm does not threaten all forms of cryptography equally. Symmetric encryption algorithms such as the Advanced Encryption Standard (AES) are not directly broken by Shor's algorithm. Although quantum computers could accelerate brute-force key searches using Grover's algorithm, this provides only a quadratic speed improvement. As a result, increasing symmetric key lengths—for example, from 128 bits to 256 bits—provides an effective countermeasure. Public-key systems based on integer factorisation or discrete logarithms, however, require entirely different cryptographic approaches.

It is important to distinguish Shor's algorithm from post-quantum cryptography. Shor's algorithm represents the quantum threat to existing public-key systems, whereas post-quantum cryptography refers to new cryptographic algorithms specifically designed to remain secure against both classical and quantum computers. Likewise, Shor's algorithm differs from Grover's algorithm, which targets unstructured search problems and has a much smaller impact on symmetric cryptography.

Today, no quantum computer possesses the scale and reliability required to use Shor's algorithm to break the large cryptographic keys used in practical communication systems. Nevertheless, the algorithm has transformed the direction of modern cryptographic research. Governments, standards organisations, and industry are actively developing and deploying post-quantum cryptographic algorithms to ensure that future communication systems remain secure as quantum computing technology continues to advance.