Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer

摘要: A digital computer is generally believed to be an efficient universal computing device; that is, it able simulate any physical device with increase in computation time by at most a polynomial factor. This may not true when quantum mechanics taken into consideration. paper considers factoring integers and finding discrete logarithms, two problems which are thought hard on classical have been used as the basis of several proposed cryptosystems. Efficient randomized algorithms given for these hypothetical computer. These take number steps input size, e.g., digits integer factored.