QUANTUM 08

Shor's
algorithm

How finding a hidden period breaks RSA

Sinclair College - Dr. Mike Libassi

TODAY

What we will cover

01RSA refresherWhy factoring matters
02Period findingThe core idea
03Quantum stepSuperposition and QFT
04Factors & scaleFrom 15 to RSA-2048
Quantum 08 · Shor's Algorithm2

01 · RSA REFRESHER

RSA rests on factoring being hard

p, q

Two secret primes. Example: 3 and 5.

N = p × q

Public modulus. Example: 15.

φ(N)

(p − 1)(q − 1). Example: 8.

e · d ≡ 1 (mod φ)

Example: e = 3, d = 11, since 33 mod 8 = 1.

Quantum 08 · Shor's Algorithm3

02 · PERIOD FINDING

Find the period of aˣ mod N

1

Pick a

Random number, e.g. a = 7

›
2

7¹, 7²

7 mod 15 = 7, 49 mod 15 = 4

›
3

7³, 7⁴

343 mod 15 = 13, 2401 mod 15 = 1

›
4

Period

Back to 1 after r = 4 steps

Listing terms one by one is the slow classical way. The quantum computer finds r without listing them.

Quantum 08 · Shor's Algorithm4

03 · THE QUANTUM STEP

Superposition, then the quantum Fourier transform

1/√Q Σx|x⟩|aˣ mod N⟩
→ QFT →measurement peaks at k = j · Q / r
reduce the fraction k / Q → its denominator reveals r

Interference concentrates the probability on outcomes spaced Q/r apart. That's the same trick as Deutsch-Jozsa, scaled up.

Quantum 08 · Shor's Algorithm5

04 · FROM PERIOD TO FACTORS

Classical math finishes the job

1

r is even

r = 4 for a = 7

›
2

ar/2 mod N

7² mod 15 = 4

›
3

GCDs

gcd(3, 15) = 3 and gcd(5, 15) = 5

›
4

Done

15 = 3 × 5

Not every a works. If r is odd, or ar/2 ≡ −1 (mod N), pick a different a and run again. Most choices succeed within a few tries.

Quantum 08 · Shor's Algorithm6

04 · REAL-WORLD SCALE

How big a quantum computer breaks RSA-2048?

EstimateQubits neededRun time
Gidney & Ekerå, 2019≈ 20 million noisy physical≈ 8 hours
Gidney, 2025under 1 million noisy physicalunder a week
Today's processorson the order of 1,000 physicalno large-scale error correction yet

The estimate dropped about twentyfold in six years through better algorithms, not bigger hardware.

Quantum 08 · Shor's Algorithm7

WRAP-UP

Key takeaways

1

Factoring N exposes the RSA private key d

2

Shor's algorithm reduces factoring to finding the period r of aˣ mod N

3

Superposition plus the QFT reveals r efficiently

4

Resource estimates keep falling, so the migration to PQC can't wait

Quantum 08 · Shor's Algorithm8

DISCUSSION

Estimates for breaking RSA dropped twentyfold in six years without new hardware. What does that suggest about planning timelines?

Connect this to "harvest now, decrypt later" in Quantum 09.

Quantum 08 · Factoring & Shor's Algorithm · Questions?  ·  Open the interactive page