Shor's algorithm could break modern encryption, but only if we build massive quantum computers.

Shor's algorithm could break modern encryption, but only if we build massive quantum computers.
Image: Intellect (generated)

In short: In 1994, Peter Shor changed cryptography forever by proving that quantum computers could factor large integers in polynomial time. This theoretical breakthrough threatens RSA and other public-key systems, yet practical implementation remains elusive due to the immense scale of error-corrected qubits required to outperform the best classical algorithms.

At its core, Shor's algorithm is a quantum method for solving the period-finding problem, which is a specific instance of the hidden subgroup problem. By reducing the task of factoring an odd composite integer into an order-finding problem, the algorithm achieves a superpolynomial speedup over classical methods like the general number field sieve. While classical computers struggle with the exponential difficulty of factoring large numbers, an ideal quantum computer could theoretically solve this in polynomial time, effectively rendering systems like RSA vulnerable.

The mechanism relies on finding the smallest positive integer r such that a raised to the power of r is congruent to 1 modulo N. Once this period is identified, the algorithm uses the difference of squares to factor N. However, this process is highly sensitive to quantum noise. As of 2026, experimental demonstrations have only succeeded with small semiprimes, often relying on prior knowledge of the solution or oversimplified circuits that mimic coin flipping rather than true quantum computation.

The path to a functional, large-scale implementation is blocked by the need for quantum error correction. Estimates suggest that beating classical computers might require millions of physical qubits to maintain stability. This challenge has become a primary driver for the development of quantum hardware and the burgeoning field of post-quantum cryptography, which seeks to design security protocols that remain resilient even in the face of powerful quantum-enabled adversaries.

Opens the Intellect+ feed with this card first. Swipe up for the next one.

Sources

To cite this card, link to https://intellectplus.co.uk/app/science-shor-s-algorithm.

How we source, check and correct cards: Editorial standards.

General information, not professional advice. Spotted an error? Flag the card or see corrections and complaints.

Intellect Plus is a visual educational discovery platform for exploring fascinating facts and ideas. Brain Food, Not Brain Rot. What is Intellect Plus?

Related

Finding something worth knowing…