On computing ordN(2) and its application

Shor proposed a polynomial time algorithm for prime factorization on quantum computers. For a given number N, he gave an algorithm for finding the order r of an element x in the multiplicative group (mod N). The method succeeds because factorization can be reduced to finding the order of an element using randomization. But the algorithm has two shortcomings, the order of the number must be even and the output might be a trivial factor. Actually, these drawbacks can be overcome in a particular case, i.e., N is an RSA modulus. In this paper, we propose a new quantum algorithm for factoring RSA modulus without the two drawbacks. Moreover, we show that the cost of the algorithm mainly depends on the calculation of ordN(2).

Authors

• Lihua Liu
• Zhengjun Cao

Keywords

No keywords are indexed for this paper.