Search This Blog

07 December 2006

Shor's Algorithm

  1. Pick a random number a < N
  2. Compute gcd(a, N). This may be done using the Euclidean algorithm.
  3. If gcd(a, N) ≠ 1, then there is a nontrivial factor of N, so we are done.
  4. Otherwise, use the period-finding subroutine (below) to find r, the period of the following function:
    f(x) = a^x\ \mbox{mod}\ N,
    i.e. the smallest integer r for which f(x + r) = f(x).
  5. If r is odd, go back to step 1.
  6. If a r/2 ≡ -1 (mod N), go back to step 1.
  7. The factors of N are gcd(ar/2 ± 1, N). We are done.
Post a Comment