Shor's Algorithm: Quantum Computing and RSA Cryptography

TechShor's Algorithm for Quantum Computing - Computerphile

TL;DR

Shor's algorithm is a quantum computing algorithm that can theoretically break RSA encryption by converting integer factorization into a period-finding problem, which quantum computers can solve exponentially faster using wave interference principles.

Key Takeaways

1RSA security depends on the difficulty of factoring large semiprimes (N = P × Q); finding P and Q breaks the cryptographic system
2Shor's algorithm reframes factorization as a period-finding problem: finding the period of a modular exponentiation function allows extraction of prime factors
3Quantum computers excel at period-finding through Fourier analysis because they can exploit constructive and destructive interference of quantum waves
4Quantum computing fundamentally relies on controlling wave interference and phase relationships, not parallel universes; this is analogous to classical physics phenomena
5Current quantum computers are too noisy to factor numbers larger than 15; practical RSA-breaking would require thousands of error-corrected qubits
6The quantum advantage comes from the Fourier transform efficiently identifying the dominant frequency (period) without testing all possibilities

Notable Quotes

“What Shaw's does is it reframes this problem. It says, 'Okay, we can't do this integer factorization. That's too difficult.' What we're going to do instead is create a function that loops periodically back to one.”
— Mike (Computerphile presenter)

“Everything from you know determining positions of atoms in a crystal lattice to the cosmic microwave background... so much of it is about finding out what are the patterns, what are the waves that contribute to these patterns.”
— Phil (physicist)

“When it comes to waves everywhere in the world around us, you know, it happens all the time... superposition in action. Every time you listen to a musical instrument, superposition. Every time you see a bloody image, superposition. It's not weird. It's not wacky.”
— Phil

“Everything we've talked about happened in this universe. We didn't have an infinite number of pixies in other universes doing the calculations for us. Just this universe is enough. More than enough.”
— Phil

Chapters

1. RSA Encryption and the Integer Factorization Problem

Introduction to RSA public-key cryptography and why integer factorization is hard. The public key contains N (a large semiprimes), while the secret primes P and Q are hidden. Factoring N classically takes hundreds of millions of years for realistic key sizes.

2. Classical Period-Finding Component of Shor's Algorithm

Shor's algorithm reformulates factorization as period-finding. It constructs a periodic function (A^R mod N) that cycles back to 1, and finding the period R enables extracting P and Q using the difference of squares and greatest common divisor.

3. Example: Factoring 15 with Classical Method

Worked example using N=15, A=2. Computing successive powers mod 15 yields the sequence 1, 2, 4, 8, 1, 2, 4, 8... with period R=4. Using the formula A^(R/2)+1 and GCD reveals factors 3 and 5.

4. Introduction to Fourier Analysis and Periodicity

Fourier transforms decompose complex patterns into component sine and cosine waves. Finding the dominant frequency in a Fourier spectrum reveals the period of a function—exactly what Shor's algorithm needs but classical computers cannot compute efficiently.

5. Fourier Transform Applied to the Periodic Function

Applying Fourier decomposition to the sequence 1, 2, 4, 8, 1, 2, 4, 8 reveals peaks in the frequency spectrum at specific values; the position of the first peak directly indicates the period (frequency = 1/period).

6. Quantum Mechanics Foundations: Waves and Superposition

Quantum systems are fundamentally based on wave behavior. Superposition is not exotic but occurs everywhere (sound waves, light, musical notes). Constructive and destructive interference of waves controls quantum behavior—nothing about parallel universes.

7. Trapped Ion Qubits and Energy Levels

A trapped ion quantum computer uses two atomic energy states (0 and 1) to represent a qubit. Microwave pulses control the probability of the qubit being in each state; laser measurements reveal the outcome but collapse the superposition.

8. Representing Quantum States as Rotating Arrows (Phasers)

Quantum states can be represented as rotating arrows (phasers) on a clock face. Arrow length squared gives measurement probability. Low-energy states rotate slowly; high-energy states rotate fast. Controlling phase (arrow alignment) enables quantum computation.

9. Quantum Fourier Transform and Measurement Collapse

The quantum Fourier transform applies microwave pulses and waiting periods to control wave interference. Measurement collapses the quantum state, forcing restart. Multiple trials are averaged to extract statistical probabilities.

10. Practical Limitations and Future Outlook

Current quantum computers can only factor numbers up to 15 due to noise and lack of error correction. Scaling to factor 2,000-bit RSA keys may take 5–100+ years. Success requires heroic efforts to isolate qubits from environmental decoherence.

Key People & Entities

Peter Shor: Mathematician who developed Shor's algorithm, a quantum algorithm for integer factorization
Jean-Baptiste Joseph Fourier: Mathematician whose Fourier transform is fundamental to decomposing functions into frequency components and central to Shor's quantum implementation
Richard Feynman: Physicist whose models and frameworks inform the visualization of quantum states using classical wave representations
Mike (Computerphile): Computer scientist presenter explaining the classical period-finding component of Shor's algorithm
Phil (Physicist): Quantum physicist explaining the quantum mechanical implementation and wave-based interpretation of Shor's algorithm

Glossary

RSA: Rivest-Shamir-Adleman; a public-key cryptographic algorithm based on the difficulty of factoring large semiprimes
Semiprimes: A number that is the product of exactly two prime numbers (not necessarily distinct)
Modular Arithmetic: Arithmetic performed on a 'clock face' where numbers wrap around at a specified modulus (e.g., mod 15 means remainders 0–14)
Fourier Transform: A mathematical technique that decomposes a function into its constituent frequencies (sine and cosine components)
Periodicity: The property of a function repeating at regular intervals; the period is the length of one complete cycle
Qubit: Quantum bit; the fundamental unit of quantum information that can exist in superposition of 0 and 1 states
Superposition: A quantum state in which a system exists in multiple states simultaneously until measured; governed by wave interference
Constructive Interference: When waves align in phase and add together to produce a larger amplitude result
Destructive Interference: When waves are out of phase and cancel each other out, producing a smaller amplitude result
Phaser: A rotating arrow representation of a quantum wave, where direction indicates phase and length indicates probability amplitude

Explore