On completely factoring any integer efficiently in a single run of an order finding algorithm

Abstract

We show that given the order of a single element selected uniformly at random from ${\mathbb{Z}}_N^{\ast }$, 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.

A minor issue in the proof of Lemma 2 has been corrected. Two references have furthermore been added, the introduction has been improved, and a number of other minor improvements have been made. No results are affected by this revision

References in corpus (4)

• Quantum algorithms for computing short discrete logarithms and factoring RSA integers
• Factoring Safe Semiprimes with a Single Quantum Query
• Odd orders in Shor's factoring algorithm
• Improving the Success Probability for Shor's Factoring Algorithm

Cited by in corpus (1)

• Revisiting Shor's quantum algorithm for computing general discrete logarithms