You are looking at a specific version 20050221:173802 of this paper.
See the latest version.
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
-
CC BY