PQC - Shor’s Algorithm

Shor’s Algorithm

Shor’s algorithm is a quantum algorithm for factoring large integers efficiently, and that is why it is such a big deal for cryptography. In practice, the security of widely used public-key systems such as RSA depends on factoring being infeasible for classical computers, but Shor’s algorithm changes that assumption.

What Shor’s Algorithm Is

Shor’s algorithm was introduced by Peter Shor in 1994 as a quantum method for factoring an integer into its prime components. The important point is not just that it factors numbers, but that it does so in polynomial time on a sufficiently capable quantum computer, compared with the much slower best known classical methods.

This makes Shor’s algorithm one of the clearest examples of a quantum algorithm with direct cryptographic impact. It is not a general-purpose “faster computer” for everything, but for factoring and related order-finding problems, it offers a dramatic speedup.

How It Works

At a high level, Shor’s algorithm reduces factoring to a problem called order finding. Given a number (N) and a chosen value (a) that is coprime to (N), the algorithm looks for the smallest positive integer (r) such that (a^r \equiv 1 \pmod N).

The quantum part of the algorithm uses superposition and interference to reveal information about that hidden period. Instead of checking factors one by one, the quantum computer evaluates many possibilities in parallel, then uses interference to amplify the right periodic structure, which is later processed classically to recover the factors.

In simplified form, the flow is:

1. Choose a random value (a).
2. Use quantum computation to find the period (r) of repeated modular exponentiation.
3. Convert that period into factors of (N) using classical number theory.
4. Repeat if the chosen value does not produce useful results.

The key insight is that the quantum computer is not “trying every factor directly.” It is extracting periodic structure, and that structure leads to the factors efficiently.

Why It Matters

Shor’s algorithm matters because it threatens the foundation of today’s public-key cryptography. RSA security relies on the difficulty of factoring large integers, and elliptic-curve systems rely on related hard problems that are also vulnerable to quantum attacks in the same broad family of concerns.

That is why post-quantum cryptography exists. NIST explicitly states that quantum computers may eventually break many widely used cryptographic systems, and its PQC program is intended to move the world toward quantum-resistant alternatives [web:6]. In other words, Shor’s algorithm is one of the main reasons organizations are planning cryptographic migration now instead of waiting for practical quantum computers to arrive.

Practical Impact Today

Shor’s algorithm does not break RSA on today’s hardware, because the quantum computers available now are not large or reliable enough to run it at the scale needed for real-world keys. However, the algorithm defines the long-term risk model, and that is enough to force planning, inventorying, and migration.

The most important operational idea is “harvest now, decrypt later.” An attacker could capture encrypted traffic today and decrypt it in the future if sufficiently powerful quantum computers become available, so sensitive data with long confidentiality lifetimes is already at risk.

Takeaway

Shor’s algorithm is the quantum algorithm that makes large-scale public-key cryptography look fragile. It is important not because it is a faster factoring trick, but because it shows that the mathematical assumptions behind RSA and similar schemes may not survive the quantum era.