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

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

1995-08-30

arxiv.org/abs/quant-ph/9508027v2

SIAM J.Sci.Statist.Comput. 26 (1997) 1484

Physics

Quantum Physics

28 pages, LaTeX. This is an expanded version of a paper that appeared in the Proceedings of the 35th Annual Symposium on Found

Scientific paper

A digital computer is generally believed to be an efficient universal computing device; that is, it is believed able to simulate any physical computing device with an increase in computation time of at most a polynomial factor. This may not be true when quantum mechanics is taken into consideration. This paper considers factoring integers and finding discrete logarithms, two problems which are generally thought to be hard on a classical computer and have been used as the basis of several proposed cryptosystems. Efficient randomized algorithms are given 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.

Affiliated with

Also associated with

No associations

Rating

Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-260194