On completely factoring any integer efficiently in a single run of an order finding algorithm
This solves the integer factorization problem for cryptography and number theory, but it is incremental as it builds on existing quantum and classical methods like Shor's and Miller's algorithms.
The paper tackles the problem of integer factorization by showing that the order of a single random element in Z_N* is sufficient to efficiently factor any integer N with high probability in polynomial time, implying that one quantum run of Shor's algorithm usually suffices, with prime factors recovered classically at negligible cost.
We show that given the order of a single element selected uniformly at random from $\mathbb Z_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.