Shor's algorithm

The Shor algorithm is an algorithm used in the mathematical branch of number theory, the means of quantum computer science. It is calculated on a quantum computer a nontrivial divisor of a composite number, making it one of the class of factorization.

For practically relevant tasks of the Shor algorithm is not applicable because it is subject to strong technical limitations. For a number one needs a quantum computer with at least qubits. A research group at IBM has a quantum computer with seven qubits used, for example, in 2001, to divide the number 15 into the factors 5 and 3.

The Shor algorithm is very important for cryptography, because it finds a non-trivial divisor essential faster than classical algorithms: While this subexponentielle, but require significantly higher than polynomial runtime, the Shor algorithm has only polynomial running time. This represents, for example, a threat to the RSA cryptosystems often used for encrypted data transmission, whose security is based precisely on the assumption that no factorization exists with polynomial running time.

The algorithm was published in 1994 by Peter W. Shor, who was employed at AT & T Bell Laboratories. The work bears the title Polynomial -Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. In a second algorithm to compute the discrete logarithm is described also, which is also referred to as Shor algorithm. In general, this term is still used for the factorization.

Properties

The Shor algorithm is a probabilistic algorithm. In some, depending on the number of repetitions in any few cases it leads to no result; the algorithm thus belongs to the class of Monte Carlo algorithms.

• Input: A composite number n
• Output: a non-trivial factor of n
• Duration: gate operations.

Expiration

The basic idea is that you can return the factorization on the determination of the order. This provision can be effectively carried out with the help of the quantum Fourier transform. One often divides the algorithm therefore in a classic part for the reduction of the problem and a quantum part that solves the remaining problem efficiently.

Classic part

Explanation:

• Why is the value in step 5, a solution? - Consider the product ( ) · ( ) =. We know after step 3 that: ≡ 0 mod n, that does not apply: ≡ 0 mod n ( step 4) and that does not apply: ≡ 0 mod n (step 3, since r is the smallest number is ≡ 0 mod n and otherwise), it follows that non-trivial divisor of n, the Euclidean algorithm for computing the gcd provides these dividers in polynomial time.
• How often do you have to repeat the process until you get a splitter? - The possibility to obtain a divider with random selection of x is at least, with k being the number of mutually different prime factors of n ( equal to 2). For example, if n is of only two prime factors composed obtained per pass with probability 1/2 a solution, the probability of failure after t steps is therefore just yet.

Quantum part

A completely different problem, also entail a significant acceleration in the quantum computer, concerns the search in a very large, unsorted database (see Grover algorithm).