[Resource Topic] 2005/051: A Note on Shor's Quantum Algorithm for Prime Factorization

Welcome to the resource topic for 2005/051

A Note on Shor’s Quantum Algorithm for Prime Factorization

Authors: Zhengjun Cao


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 .