Overview of Shor's Algorithm

Shor's algorithm hinges on a result from number theory. This result is: The function $\mathcal {F}$(a) = x^a mod n is a periodic function, where x is an integer coprime to n. In the context of Shor's algorithm n will be the number we wish to factor. When two numbers are coprime it means that their greatest common divisor is 1.

Calculating this function for an exponential number of a's would take exponential time on a classical computer. Shor's algorithm utilizes quantum parallelism to perform the exponential number of operations in one step.

The reason why this function is of utility in factoring large numbers is this:

Since $\mathcal {F}$(a) is a periodic function, it has some period r. We know that x⁰ mod n = 1, so x^r mod n = 1, and x^2r mod n = 1 and so on since the function is periodic.

Given this information and through the following algebraic manipulation:

x^r $$\equiv$$ 1 mod n

(x^r/2)² = x^r $$\equiv$$ 1 mod n

(x^r/2)² -1 $$\equiv$$ 0 mod n

and if r is an even number

(x^r/2 -1)(x^r/2 +1) $$\equiv$$ 0 mod n

We can see that the product (x^r/2 -1)(x^r/2 + 1) is an integer multiple of n, the number to be factored. So long as x^r/2 is not equal to + - 1, then at least one of (x^r/2 - 1), (x^r/2 + 1) must have a nontrivial factor in common with n. So by computing gcd(x^r/2 - 1, n), and gcd(x^r/2 + 1, n), we will obtain a factor of n, where gcd is the greatest common denominator function.