Many public key cryptosystems, such as RSA, will become obsolete if Shor's algorithm is ever implemented in a practical quantum computer. A message encrypted with RSA can be deciphered by factoring the public key *N*, which is the product of two prime numbers. Known classical algorithms cannot do this in time O((log *N*)^{k}) for any *k*, so they quickly become infeasible as *N* is increased. By contrast, Shor's algorithm can crack RSA in polynomial time. It has also been extended to attack many other public key cryptosystems.

Like all quantum computer algorithms, Shor's algorithm is probabilistic: it gives the correct answer with high probability, and the probability of failure can be decreased by repeating the algorithm.

Shor's algorithm was demonstrated in 2001 by a group at IBM, which factored 15 into 3 and 5, using a quantum computer with 7 qubits.

Table of contents |

2 Explanation of the algorithm |

- Pick a pseudo-random number
*a*<*N* - Compute gcd(
*a*,*N*). This may be done using the Euclidean algorithm. - If gcd(
*a*,*N*) ≠ 1, then it is a nontrivial factor of*N*, so we are done. - Otherwise, use the period-finding subroutine (below) to find
*r*, the period of the following function: - If
*r*is odd, go back to step 1. - If
*a*^{r/2}≡ -1 (mod*N*), go back to step 1. - The factors of
*N*are gcd(a^{r/2}± 1,*N*). We are done.

Period-finding subroutine:

- Start with a pair of input and output qubit registers with log
_{2}*N*qubits each, and initialize them to*x*runs from 0 to*N*- 1. - Construct
*f*(*x*) as a quantum function and apply it to the above state, to obtain - Perform a measurement on the output register, obtaining some result
*f*(*x*_{0}). The state of the input register becomes*A*is a normalization constant, and*j*runs from 0 to*A*- 1. - Apply the quantum Fourier transform on the input register. The
quantum fourier transform is defined by:
- Perform a measurement on the input register, obtaining some
outcome
*y*. With probability greater than 0.5,*yr/N*will lie close to an integer. - Turn
*y/N*into an irreducible fraction, and extract the denominator*r*′, which is a candidate for*r*. - Check if
*f*(*x*) =*f*(*x*+*r*′). If so, we are done. - Otherwise, obtain more candidates for
*r*by using values near*y*, or multiples of*r*′. If any candidate works, we are done. - Otherwise, go back to step 1 of the subroutine.

The integers less than *N* and coprime with *N* form a finite group under multiplication modulo *N*, which is typically denoted (**Z**/*N***Z**)^{×}. By the end of step 3, we have an integer *a* in this group. Since the group is finite, *a* must have a finite order *r*, the smallest positive integer such that

**Proof:** For simplicity, denote (*a* ^{r / 2} - 1) and (*a* ^{r / 2} + 1) by *u* and *v* respectively. *N* | *uv*, so *kN* = *uv* for some integer *k*. Suppose gcd(*u*, *N*) = 1; then *mu* + *nN* = 1 for some integers *m* and *n* (this is a property of the greatest common divisor.) Multiplying both sides by *v*, we find that *mkN* + *nvN* = *v*, so *N* | *v*. By contradiction, gcd(*u*, *N*) ≠ 1. By a similar argument, gcd(*v*, *N*) ≠ 1.

This supplies us with a factorization of *N*. If *N* is the product of two primes, this is the *only* possible factorization.