Pw. Shor, POLYNOMIAL-TIME ALGORITHMS FOR PRIME FACTORIZATION AND DISCRETE LOGARITHMS ON A QUANTUM COMPUTER, SIAM journal on computing, 26(5), 1997, pp. 1484-1509
Citations number
82
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods",Mathematics
A digital computer is generally believed to be an efficient universal
computing device; that is, it is believed able to simulate any physica
l computing device with an increase in computation time by at most a p
olynomial factor. This may not be true when quantum mechanics is taken
into consideration. This paper considers factoring integers and findi
ng discrete logarithms, two problems which are generally thought to be
hard on a classical computer and which have been used as the basis of
several proposed cryptosystems. Efficient randomized algorithms are g
iven for these two problems on a hypothetical quantum computer. These
algorithms take a number of steps polynomial in the input size, e.g.,
the number of digits of the integer to be factored.