On completely factoring any integer efficiently in a single run of an order finding algorithm
arXiv:2007.10044 · doi:10.1007/s11128-021-03069-1
Abstract
We show that given the order of a single element selected uniformly at random from , we can with very high probability, and for any integer , efficiently find the complete factorization of 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 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.
arXiv commentA 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 (6)
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Experimental realisation of Shor's quantum factoring algorithm using qubit recycling
- 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