Commenced in January 2007
Frequency: Monthly
Edition: International
Paper Count: 31903
A Post Processing Method for Quantum Prime Factorization Algorithm based on Randomized Approach

Authors: Mir Shahriar Emami, Mohammad Reza Meybodi


Prime Factorization based on Quantum approach in two phases has been performed. The first phase has been achieved at Quantum computer and the second phase has been achieved at the classic computer (Post Processing). At the second phase the goal is to estimate the period r of equation xrN ≡ 1 and to find the prime factors of the composite integer N in classic computer. In this paper we present a method based on Randomized Approach for estimation the period r with a satisfactory probability and the composite integer N will be factorized therefore with the Randomized Approach even the gesture of the period is not exactly the real period at least we can find one of the prime factors of composite N. Finally we present some important points for designing an Emulator for Quantum Computer Simulation.

Keywords: Quantum Prime Factorization, RandomizedAlgorithms, Quantum Computer Simulation, Quantum Computation.

Digital Object Identifier (DOI):

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1331


[1] R. L. Rivets and R. D. Silverman, Are Strong Primes Needed for RSA? , 22-Nov-1999
[2] R. Crandall and C. Pomerance, Prime Numbers: A Computational Perspective, Springer, ISBN: 0387252827, 2005
[3] H. Riesel, Prime Numbers and Computer Methods for Factorization, Birkhauser, Quinn-Woodbine, USA, ISBN:0-8176-3743-5
[4] J. Franke and T. Kleinjung, C. Paar, J. Pelzl, C. Priplata, C. Stahlke, M. Šimka, An Efficient Hardware Architecture for Factoring Integers with the Elliptic Curve Method, University of Bonn, University of Bochum, EDIZONE GmbH, Bonn, University of Košice, 24-2-2005
[5] O. Åsbrink, J. Brynielsson, Factoring large integers using parallel Quadratic Sieve,Apr- 2000
[6] R. P. Brent, Recent Progress and Prospects for Integer, Oxford University, Oxford, UK
[7] H. T. Riele, Factoring Large Numbers: Fun or Applied Science? , Research project: Computational Number Theory and Data Security, CWI-AR 1999
[8] R. P. Brent, Parallel Algorithms for Integer Factorization, Australian National University, Canberra, Canada Fttp://
[9] S. L. Braunstein, Quantum computation, Computer Science, University of York, UK,23-Aug 1995
[10] V. Vedral, Introduction to Quantum Information Science, Part III, Section 11,12,13, Oxford University Press, Oxford, UK, 2006
[11] M. Le Bellac, A Short Introduction to Quantum Information and Quantum Computation, Cambridge University Press, Cambridge, UK, 2006
[12] L. Ip, Shor-s Algorithm is Optimal, University of California, Berkeley, USA, 5,-Nov-2003
[13] S. J. Lomonaco and S. J. Kauffman, A Contiuous Variable Shor Algorithm, arXiv: quant-ph/0210141 v2, 8-Jun-2004
[14] L. Fortnow, Introduction of Quantum Computing from the Computer Science Perspective and Reviewing Activities, Nec Res. And Develop, Vol 44, No3, Jul-2003.
[15] A. M. Steane and E. G. Rieffel, Beyond Bits: The Future of Quantum Information Processing, Page 38, IEEE, Jan-2000
[16] R. T. Perry, The Temple of Quantum Computing, online e-book, Dec- 19,-2004
[17] C. Moore, D. Rockmore and A. Russell, Generic quantum Fourier transforms ACM Transactionson Algorithms (TALG), archive Volume 2 , Issue 4, Pages: 707 - 723 , Oct-2006 , ISSN:1549-6325
[18] J. J. Vartiainen, Unitary Transformation for Quantum Computing, Department of Engineering Physics and Mathematics, Helsinki University of Technology, Apr-2005