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 .