Quantum Algorithm for Factoring
- PDF / 118,864 Bytes
- 1 Pages / 547.087 x 737.008 pts Page_size
- 55 Downloads / 176 Views
8. Beame, P., Saks, M., Sun, X., Vee, E.: Time-space trade-off lower bounds for randomized computation of decision problems. J. ACM 50(2), 154–195 (2003) 9. Childs, A.M., Eisenberg, J.M.: Quantum algorithms for subset finding. Quantum Inf. Comput. 5, 593 (2005) 10. Kutin, S.: Quantum lower bound for the collision problem with small range. Theor. Comput. 1, 29–36 (2005) 11. Magniez, F., Nayak, A.: Quantum complexity of testing group commutativity. In: Proceedings of the International Colloquium Automata, Languages and Programming (ICALP’05), 2005, pp. 1312–1324 12. Magniez, F., Santha, M., Szegedy, M.: Quantum algorithms for the triangle problem. SIAM J. Comput. 37(2), 413–424 (2007) 13. Magniez, F., Nayak, A., Roland, J., Santha, M.: Search by quantum walk. In: Proceedings of the ACM Symposium on the Theory of Computing (STOC’07), 2007, pp. 575–584 14. Szegedy, M.: Quantum speed-up of Markov Chain based algorithms. In: Proceedings of the IEEE Conference on Foundations of Computer Science (FOCS’04), 2004, pp. 32–41 15. Yao, A.: Near-optimal time-space tradeoff for element distinctness. SIAM J. Comput. 23(5), 966–975 (1994)
Quantum Algorithm for Factoring 1994; Shor SEAN HALLGREN Department of Computer Science and Engineering, The Pennsylvania State University, University Park, PA, USA Problem Definition Every positive integer n has a unique decomposition as e a product of primes n = p1e 1 p kk , for primes numbers pi and positive integer exponents ei . Computing the decomposition p1 ; e1 ; : : : ; p k ; e k from n is the factoring problem. Factoring has been studied for many hundreds of years and exponential time algorithms for it were found that include trial division, Lehman’s method, Pollard’s method, and Shank’s class group method [1]. With the invention of the RSA public-key cryptosystem in the late 1970s, the problem became practically important and started receiving much more attention. The security of RSA is closely related to the complexity of factoring, and in particular, it is only secure if factoring does not have an efficient algorithm. The first subexponential-time algorithm is due to Morrison and Brillhard [4] using a continued fraction algorithm. This was succeeded by the quadratic sieve method of Pomerance and the elliptic curve method of Lenstra [5]. The Number Field Sieve [2,3], found in 1989, is the best known classical algorithm for factoring and runs in time exp(c(log n)1/3 (log log n)2/3 ) for some constant c. Shor’s result is a polynomial-time quantum algorithm for factoring.
Q
Key Results Theorem 1 ([2,3]) There is a subexponential-time classical algorithm that factors the integer n in time exp(c(log n)1/3 (log log n)2/3 ). Theorem 2 ([6]) There is a polynomial-time quantum algorithm that factors integers. The algorithm factors n in time O((log n)2 (log n log n)(log log log n)) plus polynomial in log n post-processing which can be done classically. Applications Computationally hard number theoretic problems are useful for public key cryptosystems. The RSA public-key cryptosystem, as
Data Loading...
