## IACR paper details

Title | A Note on Shor's Quantum Algorithm for Prime Factorization |
---|

Booktitle | IACR Eprint archive |
---|

Pages | |
---|

Year | 2005 |
---|

URL | http://eprint.iacr.org/2005/051 |
---|

Author | 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. |
---|

Search for the paper

@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
}

Download a complete BibTeX file.