Cryptology ePrint Archive: Report 2005/051

A Note on Shor's Quantum Algorithm for Prime Factorization

Zhengjun Cao

Abstract: It's well known that Shor[1] proposed a polynomial time algorithm for prime factorization by using quantum computers. For a given number $n$, he gave an algorithm for finding the order $r$ of an element $x$ (mod $n$) instead of giving an algorithm for factoring $n$ directly. The indirect algorithm is feasible because factorization can be reduced to finding the order of an element by using randomization[2]. But a point should be stressed that the order of the number must be even. Actually, the restriction can be removed in a particular case. In this paper, we show that factoring RSA modulus (a product of two primes) only needs to find the order of $2$, whether it is even or not.

Category / Keywords: foundations / Shor's quantum algorithm, RSA modulus.

Date: received 18 Feb 2005

Contact author: zjcamss at hotmail com

Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20050221:173802 (All versions of this report)

Discussion forum: Show discussion | Start new discussion