We wish to factor the number N. It will be sufficient to find even
a single factor since then we can reduce the problem to a simpler one.
First, select a number x. Euclid's algorithm (see appendix) could
be used to efficiently compute the common factors between N and x,
hence reducing our problem. We, therefore, assume that these numbers
are co-prime. Next, consider the sequence formed by the
function 
. Here 
refers
to the remainder left after division of a by b (modulo
arithmetic). It may be thought of as the hour showing on a clock having
b divisions after a hours have elapsed since the clock was
set to the zero hour (hour b). This sequence has the form:
Here the top row is just the sequence of powers 
; the bottom
row is the same sequence written in modulo arithmetic, namely
. The number r is just the first power
where 
. A close look at this sequence
shows that it has a periodic structure with period r. Using
standard algorithms this period would not be readily accessible
for a long sequence. However, with the quantum computer algorithm
described in the last section it could be calculated efficiently.
This possibility opens up a novel way to find the factors of N
as we shall now describe.
Let us suppose that we have obtained the period r by the above quantum computer algorithm [26]. If this period is even we may proceed with our factoring algorithm. If not, we must select another x and start again. A randomly chosen x will yield a suitably even period r fifty-percent of the time so not too many trials will be needed [1,2].
We now proceed with the algorithm: Having chosen an x so that the
sequence 
has an even period r, we
rewrite the expression 
as the
difference of two squares:
Expressing the left-hand-side as a product between a sum and difference we obtain
This simply says that the product of the two terms on the left is a multiple of the number N we wish to factor. Thus, either one or the other of these terms must have a factor in common with N. The final step in the algorithm then is to calculate the greatest common divisor of these terms individually with N (see the appendix for an efficient classical algorithm); any non-trivial common divisor will be a factor we have sought, thus completing our search.
As an example, consider the number N=91. Choosing x = 3 we find that
the sequence 
has the form:
A quantum computer could calculate the period in parallel, however, it
is sufficient here to see by eye that this sequence has a period of
r = 6 (since it is even we may proceed with the algorithm). Rearranging
the expression 
as discussed above we
conclude that 
. This implies
that either 
or 
will be
a non-trivial factor of 91 (where 
is the greatest common
divisor function). In fact, in this case, both terms yield a different
factor, 7 and 13, respectively. This completes the
prime factorization of 91 yielding: 
.