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: .

Wed Aug 23 11:54:31 IDT 1995