Welcome to the resource topic for
**2005/051**

**Title:**

A Note on Shor’s Quantum Algorithm for Prime Factorization

**Authors:**
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.

**ePrint:**
https://eprint.iacr.org/2005/051

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .