International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: A Note on Shor's Quantum Algorithm for Prime Factorization

Authors:
Zhengjun Cao
Download:
URL: http://eprint.iacr.org/2005/051
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2005-12388,
  title={A Note on Shor's Quantum  Algorithm for Prime Factorization},
  booktitle={IACR Eprint archive},
  keywords={foundations /  Shor's quantum algorithm,   RSA  modulus.},
  url={http://eprint.iacr.org/2005/051},
  note={ zjcamss@hotmail.com 12833 received 18 Feb 2005},
  author={Zhengjun Cao},
  year=2005
}