Shor's Algorithm

The Quantum Attack on Current Encryption

What is Shor's Algorithm?

Shor's Algorithm is a quantum computer algorithm discovered by Peter Shor in 1994. It solves two mathematical problems very efficiently on quantum computers:

1. Integer Factorization: Finding prime factors of large numbers
2. Discrete Logarithm: Finding exponents in modular arithmetic

These two problems form the foundation of most public-key encryption used today (RSA and ECC).

The Core Idea

For factoring: Shor's algorithm transforms the factoring problem into a period-finding problem, then uses quantum properties to find the period efficiently.

Key insight: While classical computers need to try all possible factors one by one (exponential time), quantum computers can explore all possibilities simultaneously and find the right answer (polynomial time).

Visualizing the Speed Difference

Method	What It Does	Time to Factor 2048-bit Number
Best Classical Algorithm	Tries all possible factors	Millions of years
Shor's Algorithm (Quantum)	Finds factors using quantum math	Hours to days (in theory)

This means a quantum computer with Shor's algorithm could break RSA-2048 in hours, while classical computers would take millions of years!

How Shor's Break Things

RSA Encryption:

Alice wants to send message to Bob:
- RSA uses: "Multiply two large primes = public key N"
- Eve tries to find the two primes from N (hard!)

Quantum computer with Shor's:
- Finds the two primes quickly
- Derives private key
- Decrypts all messages!

ECC Encryption:

ECC uses the discrete logarithm problem
- Given points G and k×G on an elliptic curve
- Find k (the private key) - hard classically

Quantum computer with Shor's:
- Finds k efficiently
- Derives private key
- Decrypts all messages!

The Magic: From Factorization to Period Finding

Shor's algorithm is clever because it doesn't factor numbers directly. Instead:

1. Pick a random number 'a' (1 < a < N)
2. Find the period 'r' of: $a^r \equiv 1 \pmod{N}$
3. Use 'r' to compute factors of N

Classical: Finding 'r' is as hard as factoring itself Quantum: Quantum Fourier transform finds 'r' efficiently

Why Shor's Works in 5 Steps

Step 1: Number Selection

• Pick random integer 'a' where 1 < a < N
• If gcd(a, N) > 1, we found a factor!

Step 2: Period Finding (The Quantum Part)

• Create quantum superposition of 0 to Q-1
• Compute: $f(x) = a^x \pmod{N}$
• Apply Quantum Fourier Transform
• Measure to find period 'r'

Step 3: Verification

• If 'r' is odd or $a^{r/2} \equiv -1 \pmod{N}$, pick new 'a'
• Otherwise, compute: $p = \gcd(a^{r/2} - 1, N)$ and $q = \gcd(a^{r/2} + 1, N)$

Step 4: Factorization Complete

• p and q are the prime factors of N
• Derive private key from p and q

Step 5: Decrypt Messages

• Use derived private key to read encrypted communications

Why Shor's Doesn't Work on ML-KEM

The Difference: Shor's algorithm requires a specific mathematical structure:

Works on:

• Integers (factoring)
• Elliptic curves (discrete logarithm)
• Problems with periodic structure

Doesn't work on:

• Lattice problems (ML-KEM's foundation)
• Learning With Errors (LWE)
• Module-Learning With Errors (MLWE)

Why Lattices?

• ML-KEM uses polynomials in a lattice structure
• Shor's cannot find the "shortest vector" problem
• No known quantum algorithm efficiently solves lattice problems (beyond small speedup from Grover's algorithm)

The Hard Problem: Shortest Vector Problem (SVP)

Given n-dimensional space with points arranged in a lattice:
┌─────────────────────────┐
│  •   •   •   •   •   •  │
│  •   •   •   •   •   •  │
│  •   •   ?   •   •   •  │ ← Find closest point to origin
│  •   •   •   •   •   •  │
│  •   •   •   •   •   •  │
└─────────────────────────┘

Classical computers: Can't find efficiently
Quantum computers: Still can't find efficiently
Shor's algorithm: Doesn't apply here!

Current Status

Classical Encryption Today:

• RSA-2048: Secure now
• ECC-P256: Secure now
• Both are used everywhere

Future with Quantum Computers:

• RSA-2048: Broken by Shor's algorithm
• ECC-P256: Broken by Shor's algorithm
• ML-KEM768: Remains secure!

Timeline Perspective:

• Shor's algorithm published: 1994
• RSA discovered: 1977
• Wait until quantum computers capable: 2030s-2040s (estimated)
• Solution: Deploy post-quantum encryption like ML-KEM now!

Summary

What Shor's Does:

• Breaks integer factorization
• Breaks discrete logarithm
• Runs in polynomial time on quantum computers
• Makes RSA and ECC obsolete

What Shor's Does NOT Do:

• Solve lattice problems
• Break ML-KEM
• Find shortest vectors
• Attack Learning With Errors

Bottom Line: Shor's algorithm is why we need post-quantum encryption like ML-KEM. While current encryption (RSA, ECC) is secure today, it will be broken when quantum computers become practical. ML-KEM, based on lattices, remains secure even against quantum computers!

---