Shor's Algorithm

In 1994, mathematician Peter Shor published an algorithm that, if run on a sufficiently powerful quantum computer, could find the prime factors of large numbers exponentially faster than any known classical algorithm. This single result is one of the main reasons quantum computing attracted serious attention from governments, industry, and the cryptography community.

The problem: factoring large numbers

Every whole number greater than 1 can be broken down into a unique set of prime numbers that multiply together to produce it — its prime factorization. For small numbers, this is easy: 15 = 3 × 5. But for very large numbers (hundreds of digits long), finding the prime factors becomes extraordinarily difficult for classical computers — the best known classical algorithms take time that grows roughly exponentially with the number of digits.

Why this matters: RSA encryption

The widely-used RSA encryption scheme — which underpins much of the security of the internet, from HTTPS websites to secure email — relies directly on the difficulty of factoring large numbers. RSA works by choosing two large prime numbers, multiplying them together to form a "public key," and keeping the original primes secret as the "private key." Anyone can use the public key to encrypt a message, but decrypting it without the private key requires factoring that large number — something that's computationally infeasible for classical computers when the numbers are large enough.

Shor's Algorithm threatens this entire foundation: a large enough, error-corrected quantum computer running Shor's Algorithm could factor these numbers efficiently, recovering the private key and breaking the encryption.

How Shor's Algorithm works (high level)

Shor's Algorithm doesn't try to factor a number directly. Instead, it cleverly transforms factoring into a different problem — finding the period of a particular mathematical function — which a quantum computer can solve efficiently using a technique called the Quantum Fourier Transform (QFT).

The overall process looks like this:

• Step 1 — Classical setup. Pick a random number and use ordinary classical computation to set up a mathematical function related to the number you want to factor.
• Step 2 — Quantum period-finding. Use a quantum computer, with qubits in superposition and the Quantum Fourier Transform, to efficiently find the "period" of that function — a hidden repeating pattern that would take a classical computer an enormous amount of time to find by brute force.
• Step 3 — Classical follow-up. Use that period, together with simple classical arithmetic (specifically, the Euclidean algorithm for finding greatest common divisors), to compute the actual prime factors.

The quantum part — period-finding via the Quantum Fourier Transform — is where the exponential speedup comes from. The QFT is itself built from a structured sequence of Hadamard and controlled-phase gates, applied to a "register" of qubits in superposition.

What it would take to actually break RSA

Despite the alarming implications, running Shor's Algorithm on cryptographically relevant numbers (thousands of bits long) is far beyond the capability of any quantum computer that exists today. Estimates for the number of high-quality, error-corrected logical qubits needed range into the thousands or millions, depending on the size of the number and the efficiency of the implementation — far more than the noisy, error-prone qubits available on current hardware.

However, the threat is taken seriously precisely because encrypted data sent today could be recorded and decrypted later, once sufficiently powerful quantum computers exist — a concern often called "harvest now, decrypt later."

The response: post-quantum cryptography

In response to this long-term threat, cryptographers have developed post-quantum cryptography (PQC) — encryption methods based on mathematical problems believed to be hard even for quantum computers (such as certain problems involving mathematical lattices). Standards bodies have been working to standardize and gradually roll out these new algorithms across the internet's infrastructure, well ahead of when large-scale quantum computers are expected to become a practical threat.

What's next?

Shor's Algorithm is the headline-grabbing example of an exponential quantum speedup. Next, let's look at a different kind of algorithm — one with a more modest, but much more broadly applicable, speedup.

Continue to: Grover's Algorithm →

Frequently Asked Questions

Has Shor's Algorithm ever actually factored a meaningful number?

Small demonstrations have factored tiny numbers (like 15 or 21) on early quantum hardware, proving the algorithm works in principle. These demonstrations are far from the scale needed to threaten real encryption, which requires factoring numbers with hundreds of digits.

Should I be worried about my data being decrypted right now?

Not from Shor's Algorithm specifically — no existing quantum computer is anywhere close to being able to run it at a relevant scale. The main reason to care today is the long-term "harvest now, decrypt later" risk, which is why organizations are gradually adopting post-quantum cryptography standards.

Does Shor's Algorithm threaten all forms of encryption?

No. It specifically threatens encryption methods based on the difficulty of factoring large numbers (like RSA) or related mathematical problems (like certain discrete logarithm problems). Other types of cryptography, including the post-quantum methods mentioned above, are designed to resist it.