Shor's Factoring Algorithm

💥 Why Shor's Algorithm Changed Everything

In 1994, Peter Shor proved that quantum computers could break RSA encryption—the system protecting most of the internet. This single result made governments and companies pour billions into quantum computing research.

❓ The Problem: Integer Factorization

Given: A large number N (e.g., 15, 21, 391, or 2048-bit RSA modulus)

Goal: Find prime factors p and q such that N = p × q

Why Is This Hard?

This asymmetry is what makes RSA encryption secure. You can multiply two primes easily (to create a public key), but factoring the result (to break it) is computationally infeasible.

⚛️ How Shor's Algorithm Works (High Level)

Shor's algorithm doesn't directly factor N. Instead, it uses a clever mathematical trick:

The Key Insight: Period Finding

Factoring reduces to finding the period of a modular function.

1. Pick a random number a (coprime to N)
2. Find the period r of the function:

   f(x) = aˣ mod N

   The period r is the smallest integer where f(x+r) = f(x) for all x

3. Use r to find factors:

   p = gcd(a^(r/2) - 1, N)
   q = gcd(a^(r/2) + 1, N)

   If r is even and a^(r/2) ≠ -1 mod N, these give non-trivial factors

🔢 Step-by-Step Algorithm

Classical Preprocessing (Steps 1-2)

1. Check if N is even: If yes, factor is 2 (trivial). Done.
2. Check if N = a^b for some integers a, b: If yes, use classical methods. Done.
3. Pick random a between 2 and N-1
4. Compute gcd(a, N): If gcd > 1, you found a factor. Done.

Quantum Period Finding (Steps 3-5)

5. Initialize quantum registers:

   Register 1: n qubits in |0⟩  (for x values)
   Register 2: n qubits in |0⟩  (for f(x) = aˣ mod N)

6. Apply Hadamard to Register 1: Create superposition

   |ψ⟩ = (1/√2ⁿ) Σₓ |x⟩|0⟩

7. Compute f(x) in superposition:

   |ψ⟩ = (1/√2ⁿ) Σₓ |x⟩|aˣ mod N⟩

   This is done using modular exponentiation circuits (hardest part to implement)

8. Measure Register 2: Collapses to some result y₀

   Now Register 1 is left in a state containing all x values where f(x) = y₀. These x values are separated by the period r.

9. Apply Quantum Fourier Transform (QFT) to Register 1:

   QFT converts the periodic state into peaks at multiples of 2ⁿ/r

10. Measure Register 1: Get a value close to k·2ⁿ/r for some integer k
11. Extract the period r: Use continued fractions to find r from the measurement

Classical Postprocessing (Step 6)

12. Check if r is even and a^(r/2) ≠ -1 mod N: If not, go back to step 3 (pick new a)
13. Compute factors:

    p = gcd(a^(r/2) - 1, N)
    q = gcd(a^(r/2) + 1, N)

14. Verify: Check if p and q are non-trivial factors. Done!

📖 Example: Factoring N = 15

Let's factor 15 using Shor's algorithm:

🌊 The Quantum Fourier Transform (QFT)

The QFT is the heart of Shor's algorithm. It's the quantum version of the classical Fast Fourier Transform (FFT).

What It Does

The QFT transforms a quantum state from the computational basis to the frequency basis:

QFT |x⟩ = (1/√N) Σₖ e^(2πixk/N) |k⟩

Why It Matters for Period Finding

If you have a periodic state (like the one after measuring Register 2), the QFT concentrates amplitude at frequencies corresponding to the period.

Complexity Advantage

💻 Implement It (Qiskit)

Full implementation of Shor's algorithm is complex (~500 lines). Here's a simplified version using Qiskit's built-in Shor function:

from qiskit.algorithms import Shor
from qiskit.utils import QuantumInstance
from qiskit import Aer

# Number to factor
N = 15

# Create a Shor instance
shor = Shor()

# Use the simulator backend
backend = Aer.get_backend('aer_simulator')
quantum_instance = QuantumInstance(backend, shots=1024)

# Run Shor's algorithm
result = shor.factor(N, quantum_instance=quantum_instance)

print(f"Factoring N = {N}")
print(f"Factors: {result.factors}")
print(f"Successful factorization: {N} = {result.factors[0][0]} × {result.factors[0][1]}")

# Output:
# Factoring N = 15
# Factors: [(3, 5)]
# Successful factorization: 15 = 3 × 5

Building QFT from Scratch (Educational)

from qiskit import QuantumCircuit
import numpy as np

def qft(circuit, qubits):
    """Apply Quantum Fourier Transform to qubits."""
    n = len(qubits)
    
    for i in range(n):
        # Apply Hadamard
        circuit.h(qubits[i])
        
        # Apply controlled phase rotations
        for j in range(i + 1, n):
            angle = 2 * np.pi / (2 ** (j - i + 1))
            circuit.cp(angle, qubits[j], qubits[i])
    
    # Reverse the order (optional, depends on convention)
    for i in range(n // 2):
        circuit.swap(qubits[i], qubits[n - i - 1])

# Example: 3-qubit QFT
qc = QuantumCircuit(3)
qft(qc, [0, 1, 2])
print(qc)

🌍 Real-World Impact

What's at Risk

What's Safe (Post-Quantum Cryptography)

• Lattice-based crypto (NTRU, Kyber) — no known quantum attack
• Hash-based signatures (SPHINCS+) — quantum-resistant
• Code-based crypto (McEliece) — safe from Shor's

Timeline Estimate

⚠️ Common Mistakes

🛠️ Practice Exercises

p = gcd(2^(6/2) - 1, 21) = gcd(8 - 1, 21) = gcd(7, 21) = 7
q = gcd(2^(6/2) + 1, 21) = gcd(8 + 1, 21) = gcd(9, 21) = 3

from qiskit.algorithms import Shor
from qiskit.utils import QuantumInstance
from qiskit import Aer

N = 21
shor = Shor()
backend = Aer.get_backend('aer_simulator')
quantum_instance = QuantumInstance(backend, shots=1024)

result = shor.factor(N, quantum_instance=quantum_instance)
print(f"21 = {result.factors[0][0]} × {result.factors[0][1]}")

🚀 What's Next?

You've learned:

• ✅ Why Shor's algorithm is revolutionary (exponential speedup)
• ✅ How period finding leads to factoring
• ✅ The role of QFT in extracting periodicity
• ✅ Real-world implications for cryptography