On completely factoring any integer efficiently in a single run of an order finding algorithm
share
We show that given the order of a single element selected uniformly at random from ℤ_N^*, we can with very high probability, and for any integer N, efficiently find the complete factorization of N in polynomial time. This implies that a single run of the quantum part of Shor's factoring algorithm is usually sufficient. All prime factors of N can then be recovered with negligible computational cost in a classical post-processing step. The classical algorithm required for this step is essentially due to Miller.
READ FULL TEXT