A Post Processing Method for Quantum Prime Factorization Algorithm based on Randomized Approach

Authors: Mir Shahriar Emami, Mohammad Reza Meybodi

Abstract:

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): doi.org/10.5281/zenodo.1059811

References:

[1] R. L. Rivets and R. D. Silverman, Are Strong Primes Needed for RSA? , 22-Nov-1999 http://citeseer.ist.psu.edu/rivest99are.html
[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 http://cr.yp.to/bib/2005/franke-ecm.pdf
[5] O. Åsbrink, J. Brynielsson, Factoring large integers using parallel Quadratic Sieve,Apr- 2000 www.nada.kth.se/~joel/qs.pdf
[6] R. P. Brent, Recent Progress and Prospects for Integer, Oxford University, Oxford, UK http://www.comlab.ox.ac.uk
[7] H. T. Riele, Factoring Large Numbers: Fun or Applied Science? , Research project: Computational Number Theory and Data Security, CWI-AR 1999 http://dbs.cwi.nl:8080/cwwwi/owa
[8] R. P. Brent, Parallel Algorithms for Integer Factorization, Australian National University, Canberra, Canada Fttp://ftp.comlab.ox.ac.uk/pub/Documents/techpapers/Richard.Brent/rpb 115.ps.gz
[9] S. L. Braunstein, Quantum computation, Computer Science, University of York, UK,23-Aug 1995 www.weizmann.ac.il/chemphys/schmuel/comp/comp.html
[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 http://citeseer.ist.psu.edu/631220.html
[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 www.phys.ntu.edu.tw/goan/Courses/D3040/PHYS_D3040.html
[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 http://portal.acm.org/citation.cfm
[18] J. J. Vartiainen, Unitary Transformation for Quantum Computing, Department of Engineering Physics and Mathematics, Helsinki University of Technology, Apr-2005 http://lib.tkk.fi/Diss/2005/isbn9512276127