Shor's Algorithm

A quantum algorithm for integer factorization

Shor’s algorithm is a quantum algorithm for finding the prime factors of an integer. It was developed by Peter Shor in 1994 and demonstrates that quantum computers could theoretically break widely used cryptographic systems like RSA.


Key Points

  1. Exponentially faster than classical factorization algorithms
  2. Uses quantum Fourier transform to find the period of a function
  3. Can factor large integers in polynomial time on a quantum computer
  4. Threatens current RSA encryption if large-scale quantum computers become practical
  5. Combines classical and quantum computation steps

Algorithm Overview

  1. Choose a random integer a that is coprime to N (the number to factor)
  2. Use quantum period finding to determine the period r of the function f(x) = a^x mod N
  3. If r is even and a^(r/2) ≠ ±1 mod N, compute gcd(a^(r/2) ± 1, N) to find factors
  4. The quantum speedup comes from efficiently finding the period using quantum Fourier transform

Applications and Impact

  1. Demonstrates the potential power of quantum computing for specific problems
  2. Motivates research into post-quantum cryptography
  3. Shows quantum advantage for number-theoretic problems
  4. Requires error correction and large qubit counts for practical implementation