Quantum Cryptography: Shor’s Algorithm

Explore Shor’s algorithm and its implications for RSA.

← Quantum Computing projects

Learn Mathematics Quantum Computing

Question

How does quantum period finding turn integer factorization into a tractable task?

Shor's algorithm uses a quantum period to expose the arithmetic structure of a composite number.
Shor's algorithm uses a quantum period to expose the arithmetic structure of a composite number.

Goals

  • Explain the link between period finding, factorization, and RSA security.
  • Run the main stages of Shor's algorithm on small integers.

Method

Use a quantum routine to find a period, then recover factors with classical arithmetic.

  • Choose a number \(N\) and a base \(a\), then study the periodic powers of \(a\) modulo \(N\).
  • Model modular exponentiation and the quantum Fourier transform in a small circuit or simulator.
  • Estimate the period and use greatest common divisors to obtain candidate factors.