🔐

Topic 8 of 12

Shor's Factoring Algorithm

Shor's algorithm (1994) factors an integer N in O((log N)³) time — exponentially faster than the best classical algorithms, which run in sub-exponential but super-polynomial time. Since RSA encryption relies on the hardness of factoring large numbers, a large-scale quantum computer running Shor's algorithm would break RSA and most public-key cryptography currently protecting the internet.

Key Concepts

Period Finding

Shor's key insight: factoring N reduces to finding the period

r

of the function

f(x) = a^x \bmod N

for a random

a

coprime to

N

. If we find

r

, then

a^r \equiv 1 \pmod{N}

, and with high probability

\gcd(a^{r/2} \pm 1, N)

gives non-trivial factors of

N

Quantum Period Finding

The QFT detects the period

r

exponentially efficiently. Prepare a uniform superposition of all

x

values, apply the modular exponentiation

|x\rangle|0\rangle \to |x\rangle|a^x \bmod N\rangle

, measure the second register (which collapses the first to a periodic superposition), then apply QFT and measure to extract

N/r

Continued Fractions

After the QFT measurement yields a rational approximation

s/q

j/r

for some integer

j

, the classical continued fractions algorithm recovers

r

efficiently. This is the classical post-processing step that converts the quantum frequency measurement into the actual period.

RSA Cryptography

RSA encryption uses a public key

(N, e)

where

N = pq

is a product of two large primes. Security relies on the assumption that factoring

N

is computationally infeasible classically (sub-exponential time). Shor's algorithm breaks this assumption — a 4000-logical-qubit quantum computer could factor 2048-bit RSA keys.

Post-Quantum Cryptography

Cryptographic schemes resistant to quantum attacks, standardized by NIST in 2024. Leading approaches: lattice-based cryptography (Learning With Errors), hash-based signatures, and code-based cryptography. These problems are believed to resist both classical and quantum attacks.

Modular Exponentiation

Computing

a^x \bmod N

for all

x

simultaneously in quantum superposition requires

O(n^3)

gates (where

n = \log N

) using repeated squaring and modular arithmetic circuits. This is the most resource-intensive part of Shor's algorithm on real hardware.

Key Equations

Reduction to Period Finding

N = pq \implies \text{find period } r \text{ of } a^x \bmod N \implies p,q = \gcd(a^{r/2}\pm 1, N)

Factoring reduces to period finding via number theory.

Period Condition

a^r \equiv 1 \pmod{N}, \quad \gcd(a,N) = 1

r is the multiplicative order of a modulo N.

Factor Extraction

\gcd(a^{r/2}-1,\, N) \text{ and } \gcd(a^{r/2}+1,\, N)

These GCDs give non-trivial factors of N with probability ≥ 1/2.

Shor's Complexity

T_{\text{Shor}}(N) = O((\log N)^3) \ll T_{\text{classical}} = e^{O((\log N)^{1/3}(\log\log N)^{2/3})}

Shor is polynomial; the best classical factoring (GNFS) is sub-exponential.

Worked Example

Factoring N=15 with a=7

Problem

Use period finding to factor $N=15$ with base $a=7$ .

Solution

Compute powers of 7 mod 15 to find the period:

7^1 \bmod 15 = 7,\quad 7^2 \bmod 15 = 49 \bmod 15 = 4

7^3 \bmod 15 = 7\cdot4 \bmod 15 = 28 \bmod 15 = 13,\quad 7^4 \bmod 15 = 7\cdot13 \bmod 15 = 91 \bmod 15 = 1

Period $r=4$ . Now compute the factors:

\gcd(7^2 - 1,\, 15) = \gcd(48,\, 15) = \gcd(3,\, 15) = 3

\gcd(7^2 + 1,\, 15) = \gcd(50,\, 15) = \gcd(5,\, 15) = 5

Answer Factors of 15: 3 and 5. (15 = 3 × 5)

Practice

Exercises

6 problems

1 of 6

$7^2 \bmod 15 = ?$

Your answer

2 of 6

$\gcd(48, 15) = ?$

Your answer

3 of 6

Find the period $r$ of $2^x \bmod 15$ : $2^1=2, 2^2=4, 2^3=8, 2^4=16\bmod15=1$ . What is $r$ ?

Unlock Exercise 3

Subscribe to PhysWeb Pro to access all exercises and track your progress.

Upgrade to Pro →

4 of 6

$2^{10} \bmod 15 = ?$ (Use period $r=4$ : $10 = 2\times4+2$ , so answer $= 2^2 \bmod 15$ .)

Unlock Exercise 4

Subscribe to PhysWeb Pro to access all exercises and track your progress.

Upgrade to Pro →

5 of 6

$\gcd(2^{4/2}-1, 15) = \gcd(3, 15) = ?$

Unlock Exercise 5

Subscribe to PhysWeb Pro to access all exercises and track your progress.

Upgrade to Pro →

6 of 6

Shor's algorithm time complexity is $O((\log N)^k)$ . What is $k$ ?

Unlock Exercise 6

Subscribe to PhysWeb Pro to access all exercises and track your progress.

Upgrade to Pro →

Key Takeaways

Shor's algorithm factors $N$ in $O((\log N)^3)$ time — exponentially faster than any known classical method.
The key step is period finding: find $r$ s.t. $a^r \equiv 1 \pmod N$ ; then $\gcd(a^{r/2}\pm1, N)$ gives factors.
The QFT efficiently extracts the period $r$ from the periodic amplitude pattern of $|a^x \bmod N\rangle$ .
RSA security relies on factoring being hard classically; Shor's algorithm breaks this assumption.
Post-quantum cryptography (lattice-based, hash-based) is being standardized to resist quantum attacks.