Paper 2005/051

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.

Metadata
Available format(s)
PDF PS
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
Shor's quantum algorithmRSA modulus.
Contact author(s)
zjcamss @ hotmail com
History
2005-02-21: received
Short URL
https://ia.cr/2005/051
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2005/051,
      author = {Zhengjun Cao},
      title = {A Note on Shor's Quantum  Algorithm for Prime Factorization},
      howpublished = {Cryptology ePrint Archive, Paper 2005/051},
      year = {2005},
      note = {\url{https://eprint.iacr.org/2005/051}},
      url = {https://eprint.iacr.org/2005/051}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.