A Note on Shor＇s Quantum Algorithm

Shor proposed a polynomial time algorithm for computing the order of one element in a multiplicative group using a quantum computer. Based on Miller＇s randomization, he then gave a factorization algorithm. But the algorithm has two shortcomings, the order must be even and the output might be a trivial factor. Actually, these drawbacks can be overcome if the number is an RSA modulus. Applying the special structure of the RSA modulus, an algorithm is presented to overcome the two shortcomings. The new algorithm improves Shor＇s algorithm for factoring RSA modulus. The cost of the factorization algorithm almost depends on the calculation of the order of 2 in the multiplication group.     

A Note on Shor’s Quantum Algorithm

Introduction Factoring integers is generally thought to behard on a classical computer. But it is now heldthat prime factorization can be accomplished inpolynomial time on a quantum computer. This re-markable work is due to Shor[1]. For a given num-ber n, he gave a quantum computer algorithm forfinding the order r of an element x (mod n) insteadof giving a quantum computer algorithm for factor-ing n directly. The indirect algorithm is feasiblebecause factorization can be reduced to finding th…