Shor's algorithm hinges on a result from number theory. This
result is:
The function
(*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
(*a*) is a periodic function, it has some
period *r*. We know that
*x*^{0} 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/2})^{2} = *x*^{r} 1 mod *n*

(*x*^{r/2})^{2} -1 0 mod *n*

and if

(*x*^{r/2} -1)(*x*^{r/2} +1) 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.