**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 format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

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

**Short URL: **ia.cr/2005/051

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]