A Post Processing Method for Quantum Prime Factorization Algorithm based on Randomized Approach
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.
[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
[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
@article{"International Journal of Engineering, Mathematical and Physical Sciences:53878", author = "Mir Shahriar Emami and Mohammad Reza Meybodi", title = "A Post Processing Method for Quantum Prime Factorization Algorithm based on Randomized Approach", 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.", volume = "1", number = "10", pages = "473-5", }
