next up previous
Next: Prospects: Up: Quantum computation: a tutorial Previous: Quantum parallelism: Period

Factoring numbers:

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

next up previous
Next: Prospects: Up: Quantum computation: a tutorial Previous: Quantum parallelism: Period

Samuel L.~Braunstein
Wed Aug 23 11:54:31 IDT 1995