Tutorial on Shor's Quantum Factoring Algorithm

Miller [1976] gave a randomized polynomial-time reduction of the problem of factoring a number N to the problem of determining the order of a random element in the multiplicative group mod N. Shor's algorithm actually solves the latter problem.

Here is a high-level description of Shor's algorithm for the latter problem.

Two sections that could be added to this tutorial (volunteers?) are:


Neal Young <Neal.Young@dartmouth.edu>
Last modified: Tue Dec 16 00:04:02 EST 1997