30-10-2009, 04:16 PM
[attachment=376]
Shors Algorithm
Abstract
In contrast to finding and multiplying of large prime numbers, no efficient classical algorithm for the factorization of a large number is known. The multiplication of large prime numbers is therefore a one-way function i.e. a function which can be evaluated easily in one direction, while its inversion is practically impossible. While it is generally believed that efficient prime factorization on a classical computer is impossible, an efficient algorithm for quantum computers has been proposed in 1994 by P.W.Shor.