qc000021.htm

5.4 Shor’s algorithm

The factoring problem requires finding a non-trivial factor of a given a composite integer. More precisely, if

is given and known to be composite, find a non-trivial factor of it, that is,

such that

divides

(

Multiplying large numbers is computationally easy. In contrast, no conventional polynomial – in the length of its input measured in bits – algorithm for the factorization of large numbers is known.

The best known published conventional algorithm, the so-called quadratic sieve, needs

operations for factoring a binary number of

bits; this is exponential with the input size as

. See Lenstra and Lenstra _[87], Gruska _[67]. There exist sub-exponential O(

) randomized algorithms for factoring.

Why are we concerned with these subtleties regarding such a “simple" problem as factoring of integers? The multiplication of large prime numbers is a “one-way function" i.e. a function which can easily be computed, while computing its inversion is “thought" (but not proven) to be practically impossible. One-way functions play a major role in digital cryptography and are essential to public key crypto-systems where the key for encoding is public and only the key for decoding remains secret. An example is the RSA method invented in Rivest, Shamir _and Adleman _[118]. Their cryptographic algorithm is based on the “one-way" character of multiplying two large prime numbers

(typically of 512 or 1024 digits). Encription seems to be secure provided it is not feasible to get

from their product

The RSA method is one of the most popular public key systems and is implemented in many communication programs.

Figure 16: Peter Shor

According to Hughes [75] conventional factoring perspectives with the best available method in 1997 (quadratic sieve) on a network of 1,000 workstations is presented in Table 5.

Year/Number of bits			4096
_
2006	years	years	years

2024	years	years	years

2042	days	years	years

Table 5: Perspectives of factoring on conventional computers.

While it is generally believed (although not proven) that efficient prime factorization on a conventional computer is impossible, an efficient algorithm for quantum computers has been proposed in 1994 by Shor _[122]; see also Beckman, _Shari, _Devabhaktuni _and Preskill _[ 7], Ekert and Jozsa [56].

A key idea is to reduce factoring to the problem of finding the period of an integer function. Consider first a composite

and let us find an integer

such that

, and

. If

is an integer satisfying the above conditions, then

is a multiple of

, but

is not divisible by

nor is

, so there exists a non-trivial factor

that divides say

. A factor of

can then be found by Euclid’s algorithm

in O(

) time: we compute

and

For example, if

, then

is a solution of

that verifies the above requirements;

so 5 and 3 are non-trivial divisors of 15.

Let

be the set of all integers

in the interval

co-primes with

, that is

Pick

and define the function

(

The function

is periodic, that is there exists an integer

such that

, for every

. The smallest

such that

is called the order of

and is denoted by

If the period

is even, then the equation

can be written in the following equivalent form:

The product

is a multiple of

, hence, unless

both factors of the product must have a non-trivial factor in common with

. Consequently, the following algorithm can be used:

Step 1. Choose a uniformly distributed integer

.
Step 2. If

, then we have a factor of

and stop.
Step 3. Compute the period

of the function

.
Step 4. If

is odd or

,
then go to Step 1; otherwise, compute

to get a factor of

and stop. _

Note that in case

, where

is a prime and

, if

and

, then

is odd or

. So, this case is excluded by the above algorithm. However, we don’t lose generality because power of primes can be factorized by conventional computers in polynomial time.

What are the chances of finding a factor of

by computing

and

? This question is answered by the following evaluations (see, for example, Shor _[122] or Gruska [67]):

	Assume that is not a power of a prime. If is selected uniformly distributed in , then the probability to find a even such that and is greater or equal to .
	If is odd and is selected uniformly distributed in , then the probability that is even is greater or equal to .
	The probability of picking an element , uniformly distributed in , such that is even, and is greater or equal to .

This analysis leads to the following conclusion:

If there is a polynomial time deterministic/probabilistic/quantum algorithm to compute the period of the function , for every , then there exists a deterministic/probabilistic/quantum algorithm to factorize any integer .

Unfortunately, there is no known polynomial time deterministic/probabilistic algorithm to compute the period of the function

! Next we will follow Shor _[122] in presenting a polynomial time quantum algorithm to compute the period of the function

Let

be quantum function

of the integer function

with the unknown period

. To determine

, we need two registers, with the sizes of

and

qubits, which should be reset to

As a first step we produce, using the Hadamard transform

, a homogenous superposition of all basis vectors in the first register by applying an operator

Applying

to the resulting state gives:

A measurement of the second register with the result

with

reduces the state to

The measurement selects the values

, where

is the largest integer such that

, and

is chosen randomly (by measurement). So,

. The post-measurement state

of the first register consists only of basis vectors of the form

. Reason:

, for all

then

where

is a multiple of

, then

is a multiple of

, and

otherwise. But even if

is not a power of

, the spectrum of

shows distinct peaks with a period of

because

This is also the reason we use a register of

qubits when

: it guarantees at least

elements in the above sum and thus a peak width of order O

Now measure the first register: we will get a value

close to

with

. This can be written as

. We can think of this result as a rational approximation

with

for dyadic number

. An efficient classical algorithm for solving this problem using continued fractions is described in Hardy and Wright [ 68] and is implemented in the denominator function.

Since the form of a rational number is not unique,

and

are only determined by

. The probability that

and

are co-prime is greater then

, so only O

trials are necessary to achieve a probability of success as close to one as desired; in fact, as observed by Shor _[122], the expected number of trials can be decreased to a constant.

Shor’s _algorithm is probabilistic, so it may fail. The main point is that it shows that factoring can be checked in polynomial time by a quantum algorithm. However, there is no proof that factoring cannot be checked in polynomial time by a deterministic conventional algorithm. If efficient ways to simulate quantum computers on conventional machines will be found, then Shor’s _algorithm will be transformed into an efficient conventional procedure for factoring. However, this possibility seems very improbable, but not impossible. Recently, Agrawal, Kayal and Saxena [1] have obtained a simple deterministic polynomial-time algorithm for primality, a close relative problem to factoring. Hughes [75] has estimated (see Table 6) the time needed for factoring by quantum computers (with minimal clock speed of 100 MHz).

So, according to Tables 5, 6, using RSA with 2,048-bit numbers may be safe for the next 50 years if no quantum computer will be constructed by then; in the opposite case, even working with 4,096-bit numbers may not be safe if quantum computers become available!