Shor’s Algorithm

Shor’s Algorithm is one of the most famous quantum algorithms. Developed by Peter Shor in 1994, it can factor large numbers exponentially faster than the best known classical algorithms. This makes it a direct threat to many of the encryption systems we rely on today.

It is often cited as the “killer app” that first showed the true potential of quantum computing.

Why Shor’s Algorithm Matters

Most modern encryption (RSA, ECC) depends on the extreme difficulty of factoring very large numbers. Shor’s algorithm could break this assumption. This is why governments and companies are racing to develop both quantum computers and “post-quantum” encryption that can resist it.

The Layers

Foundation — Combines classical number theory with the Quantum Fourier Transform.

Period Finding — The core quantum part that finds the repeating pattern in a mathematical function.

Factoring — Once the period is known, classical post-processing quickly reveals the prime factors.

Impact — Demonstrates clear exponential speedup for a practical, real-world problem.

Getting Started

While running Shor’s on large numbers isn’t practical yet, you can run simplified versions using Qiskit Textbook. It has excellent step-by-step implementations that show exactly how the algorithm works.

Ready to explore? Run the textbook example of Shor’s algorithm on small numbers. Even seeing it work on 15 or 21 helps you understand why this single algorithm created so much excitement (and concern) around quantum computing.

Shor’s algorithm remains one of the strongest examples of quantum advantage and is essential knowledge for anyone serious about the field.