# NAME

` shor - A short demonstration of Quantum::Entanglement`

# SYNOPSIS

` ./shor.pl [number to factor (>14)]`

# DESCRIPTION

This program implements Shor's famous algorithm for factoring numbers. A brief overview of the algorithm is given below.

## The important maths

Given a number **n** which we are trying to factor, and some other number which we have guessed, **x**, we can say that:

` x**0 % n == 1 (as x**0 = 1, 1 % n =1)`

There will also be some other number, **r** such that

` x**r % n == 1`

or, more specifically,

` x**(kr) % n ==1`

in other words, the function

` F(a) = x**a % n`

is periodic with period **r**.

Now, starting from

```
x**r = 1 % n
x**(2*r/2) = 1 % n
(x**(r/2))**2 - 1 = 0 % n
```

and, if r is an even number,

` (x**(r/2) - 1)*(x**(r/2) + 1) = 0 mod n`

or in nice short words, the term on the left is an integer multiple of **n**. So long as x**(r/2) != +-1, at least one of the two brackets on the left must share a factor with **n**.

Shor's alorithm provides a way to find the periodicity of the function F and thus a way to calculate two numbers which share a factor with n, it is then easy to use a classical computer to find the GCD and thus a factor of **n**.

# The steps of the algorithm

## 1. Remove early trivial cases

We have efficient classical methods for finding that 2 is a factor of 26, so we do not need to use this method for this.

## 2. Pick an integer

Chose a number **q** so that `n**2 <= q <= 2n**2`

, this is done on a classical computer. (This is the size we will use for our quantum register.)

## 3. Select at random a number coprime to n

Think of some number less than **n** so that **n** and **x** do not share a common factor (if they do, we already know the answer...).

## 4. Fill a quantum register with integers from 0..q-1

This is where we create our first entangled variable, and is the first non-classical step in this algorithm.

## 5. Calculate F, store in a second register

We now calculate ` F(a) = x**a % n`

where a represents the superposition of states in our first register, we store the result of this in our second register.

## 6. Look at register2

We now look at the value of register two and get some value **k**, this forces register1 into a state which can only collapse into values satisfying the equation

` x**a % n = k`

The probability amplitudes for the remaining states are now all equal to zero, note that we have not yet looked directly at register1.

## 7. Find period of register1

We now apply a fourier transform to the amplitudes of the states in register1, storing the result as the probability amplitudes for a new state with the values of register1. This causes there to be a high probability that the register will collapse to a value which is some multiple of `q/r`

.

## 8. Observe register1

We now observe register1, and use the result to calculate a likely value for **r**. From this we can easily calculate two numbers, one of which will have a factor in common with n, by applying an efficient classical algoirthm for finding the greatest common denominator, we will be able to find a value which could be a factor of **n**.

# Things to remember

This algorithm does not claim to produce a factor of our number the first time that it is run, there are various conditions which will cause it to halt mid-way, for instance, the FT step can give a result of 0 which is clearly useless. The algorithm is better than any known classical one because the expectation value of the time required to get a correct answer is still O(n).

This also cannot factor a number which is prime (it being, as it were, prime) and also cannot factor something which is a prime power (25, say).

# COPYRIGHT

This code is copyright (c) Alex Gough (alex@rcon.org )2001. This is free software, you may use, modify and redistribute it under the same terms as Perl itself.

# BUGS

This is slow, being run on classical computers, ah well.