Extending Regev's factoring algorithm to compute discrete logarithms

Abstract

Regev recently introduced a quantum factoring algorithm that may be perceived as a $d$-dimensional variation of Shor's factoring algorithm. In this work, we extend Regev's factoring algorithm to an algorithm for computing discrete logarithms in a natural way. Furthermore, we discuss natural extensions of Regev's factoring algorithm to order finding, and to factoring completely via order finding. For all of these algorithms, we discuss various practical implementation considerations, including in particular the robustness of the post-processing.

arXiv commentA number of improvements have been made, and further details on the robustness of the post-processing and other practical implementation considerations added

References in corpus (5)

• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits
• Quantum algorithms for computing short discrete logarithms and factoring RSA integers
• Quantum Complexity for Discrete Logarithms and Related Problems
• On the success probability of quantum order finding

Cited by in corpus (6)

• Quantum Complexity for Discrete Logarithms and Related Problems
• Quantum resource estimates for computing binary elliptic curve discrete logarithms
• The Jacobi Factoring Circuit: Quantum Factoring with Near-Linear Gates and Sublinear Space and Depth
• A high-level comparison of state-of-the-art quantum algorithms for breaking asymmetric cryptography
• Simulation of Shor algorithm for discrete logarithm problems with comprehensive pairs of modulo p and order q
• Quantum Algorithms for Discrete Log Require Precise Rotations