Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2311.05545 · Lecture notes in computer science

Extending Regev’s Factoring Algorithm to Compute Discrete Logarithms

Martin Ekerå, Joel Gärtner

Published Jan 1, 2024• 14 citations
arXivHTMLPDF
DOI
10.1007/978-3-031-62746-0_10

Related papers

Polynomial time algorithms for discrete logarithms and factoring on a quantum computer

Peter W. Shor

Lecture notes in computer science•Jan 1, 1994•130 citations

Quantum Algorithms for Computing Short Discrete Logarithms and Factoring RSA Integers

Martin Ekerå, Johan Håstad

arXiv:1702.00249•Lecture notes in computer science•Jan 1, 2017•64 citations

Modifying Shor's algorithm to compute short discrete logarithms.

Martin Ekerå

•Jan 1, 2016•6 citations

Regev's reduction as a candidate quantum algorithm for the discrete logarithm problem in finite abelian groups

M. Isabel Franco Garrido, André Chailloux

In this article, we investigate whether combining Regev's reduction with the Cheng-Wan reduction can yield an alternative quantum algorithm for the discrete logarithm problem (DLOG) in finite abelian groups. Cheng and Wan reduce DLOG over finite fields to bounded-distance decoding of low-rate Reed-Solomon codes at a large decoding radius. Regev's reduction, in turn, exploits a decoder for the high-rate dual code with a lower noise level to obtain a quantum algorithm for decoding the original low-rate code at a larger radius. The Cheng-Wan instances therefore provide a natural setting in which to explore the power of Regev's framework. We first extend the Cheng-Wan reduction to the discrete logarithm problem in finite abelian groups, assuming access to embeddings of their cyclic factors. We also establish NP-hardness of Reed-Solomon bounded-distance decoding at asymptotically vanishing rate, reaching the rate regime relevant to Cheng-Wan, while the radius at which we establish hardness remains beyond the Cheng-Wan radius. We then instantiate Regev's reduction at the Cheng-Wan parameters and, under a conjecture on the performance of the induced BDD algorithm on the structured Cheng-Wan instances, characterize the noise threshold for the quantum decoding problem(QDP) sufficient to solve DLOG. We evaluate known decoders in this regime and show that a quantum decoder based on unambiguous state discrimination(USD) enables Regev's reduction to reach a strictly stronger decoding regime than the standard classical Reed-Solomon decoders we consider. Nevertheless, the QDP noise threshold required by the Cheng-Wan reduction is asymptotically 4/3 times that achieved by USD. Going beyond the USD framework, we show that every Cheng-Wan instance can be solved through Regev's reduction using a suitable Pretty Good Measurement and its inverse, although no efficient implementation of it is known.

quant-pharXiv:2605.03972•May 6, 2026•0 citations

On factoring integers, and computing discrete logarithms and orders, quantumly

Martin Ekerå

This thesis contains a collection of efficient quantum algorithms and classical pre- and post-processing algorithms for various number- and group-theoretical problems with concrete cryptanalytical applications. More specifically, the focus is on the integer factoring problem (IFP), the discrete logarithm problem (DLP), and the order-finding problem (OFP), and on certain important variations of these problems. It is for example explained how the OFP and complete IFP may be solved efficiently in a single run of a reduced version of Shor's algorithm for the OFP with very high success probability, as evidenced by a lower bound that is 1 − o(1), how the short DLP in groups of unknown order may be solved efficiently and with an advantage over Shor's algorithm for the DLP (that furthermore requires the order to be known), as evidenced by a lower bound on the single-run success probability that is 1 − o(1), how the RSA IFP may be solved efficiently and with an advantage over Shor's algorithm for the IFP, by reducing the RSA IFP to a short DLP, how the DLP may heuristically be solved efficiently, and with high success probability that is 1 − o(1), in a single run of a reduced version of Shor’s algorithm for the DLP that admits efficient implementation, how the DLP may be solved in groups of unknown order, such as Schnorr groups, by jointly solving an OFP and a DLP at lower overall cost but higher per-run cost compared to first solving the OFP and then the DLP, how tradeoffs — between the number of group operations that are evaluated quantumly and the number of runs that are required — may be achieved in all of the aforementioned algorithms, and how all of the aforementioned algorithms may be simulated efficiently classically, for arbitrary large cryptographically relevant problem instances, when the solution to the instance is known, enabling the number of runs required when performing tradeoffs to be tightly estimated. It is furthermore for example explained how Regev's recent quantum algorithm for the IFP may be extended to the DLP and OFP, yielding i) a reduction in the circuit size and depth by a factor compared to Shor for these problems when working in , for N an n-bit integer, at the expense of performing runs, and ii) slight improvements of Regev's orginal algorithm for the IFP, how the above algorithms may be simulated efficiently classically, for large special-form problem instances that are classically tractable, and that Regev’s post-processing, and the post-processing for our extensions, are robust to an arbitrarily large fraction < 1 of the runs being bad. The above has implications for cryptography based on the intractability of the IFP and DLP — including but not limited to for widely used schemes such as RSA, DSA and Diffie–Hellman. The algorithms in this thesis are all derived from, and make notable improvements to, the seminal works of Shor. Some of the contributions are joint works with other authors.

•Jan 1, 2024•0 citations

Regev’s Attack on Hyperelliptic Cryptosystems

Razvan Barbulescu, Gaetan Bisson

An algorithm of Ekerå and Gärtner, inspired by Regev’s factoring algorithm, computes discrete logarithms in multiplicative groups of prime fields. Asymptotically, it has the same qubit and gate complexity as Shor’s algorithm but splits the computation into d independent, parallel runs. The optimal value of this parameter is d∼n where n is the bit size of the cryptographic group. We propose an extension of this algorithm to hyperelliptic curves. For curves of genus g∼n, which are not used in cryptography, we prove unconditionally that the optimal number of parallel runs d∼n can still be achieved. For genus-two curves, we propose a heuristic algorithm. While its runtime speedup is difficult to quantify in general, we show that it can be expected to use up to d=8 parallel runs for specific curves relevant to cryptography, including GLV-friendly and pairing-friendly curves.

Cryptography•Aug 28, 2026•0 citations
In this article, we investigate whether combining Regev's reduction with the Cheng-Wan reduction can yield an alternative quantum algorithm for the discrete logarithm problem (DLOG) in finite abelian groups. Cheng and Wan reduce DLOG over finite fields to bounded-distance decoding of low-rate Reed-Solomon codes at a large decoding radius. Regev's reduction, in turn, exploits a decoder for the high-rate dual code with a lower noise level to obtain a quantum algorithm for decoding the original low-rate code at a larger radius. The Cheng-Wan instances therefore provide a natural setting in which to explore the power of Regev's framework. We first extend the Cheng-Wan reduction to the discrete logarithm problem in finite abelian groups, assuming access to embeddings of their cyclic factors. We also establish NP-hardness of Reed-Solomon bounded-distance decoding at asymptotically vanishing rate, reaching the rate regime relevant to Cheng-Wan, while the radius at which we establish hardness remains beyond the Cheng-Wan radius. We then instantiate Regev's reduction at the Cheng-Wan parameters and, under a conjecture on the performance of the induced BDD algorithm on the structured Cheng-Wan instances, characterize the noise threshold for the quantum decoding problem(QDP) sufficient to solve DLOG. We evaluate known decoders in this regime and show that a quantum decoder based on unambiguous state discrimination(USD) enables Regev's reduction to reach a strictly stronger decoding regime than the standard classical Reed-Solomon decoders we consider. Nevertheless, the QDP noise threshold required by the Cheng-Wan reduction is asymptotically 4/3 times that achieved by USD. Going beyond the USD framework, we show that every Cheng-Wan instance can be solved through Regev's reduction using a suitable Pretty Good Measurement and its inverse, although no efficient implementation of it is known.
This thesis contains a collection of efficient quantum algorithms and classical pre- and post-processing algorithms for various number- and group-theoretical problems with concrete cryptanalytical applications. More specifically, the focus is on the integer factoring problem (IFP), the discrete logarithm problem (DLP), and the order-finding problem (OFP), and on certain important variations of these problems. It is for example explained how the OFP and complete IFP may be solved efficiently in a single run of a reduced version of Shor's algorithm for the OFP with very high success probability, as evidenced by a lower bound that is 1 − o(1), how the short DLP in groups of unknown order may be solved efficiently and with an advantage over Shor's algorithm for the DLP (that furthermore requires the order to be known), as evidenced by a lower bound on the single-run success probability that is 1 − o(1), how the RSA IFP may be solved efficiently and with an advantage over Shor's algorithm for the IFP, by reducing the RSA IFP to a short DLP, how the DLP may heuristically be solved efficiently, and with high success probability that is 1 − o(1), in a single run of a reduced version of Shor’s algorithm for the DLP that admits efficient implementation, how the DLP may be solved in groups of unknown order, such as Schnorr groups, by jointly solving an OFP and a DLP at lower overall cost but higher per-run cost compared to first solving the OFP and then the DLP, how tradeoffs — between the number of group operations that are evaluated quantumly and the number of runs that are required — may be achieved in all of the aforementioned algorithms, and how all of the aforementioned algorithms may be simulated efficiently classically, for arbitrary large cryptographically relevant problem instances, when the solution to the instance is known, enabling the number of runs required when performing tradeoffs to be tightly estimated. It is furthermore for example explained how Regev's recent quantum algorithm for the IFP may be extended to the DLP and OFP, yielding i) a reduction in the circuit size and depth by a factor compared to Shor for these problems when working in , for N an n-bit integer, at the expense of performing runs, and ii) slight improvements of Regev's orginal algorithm for the IFP, how the above algorithms may be simulated efficiently classically, for large special-form problem instances that are classically tractable, and that Regev’s post-processing, and the post-processing for our extensions, are robust to an arbitrarily large fraction < 1 of the runs being bad. The above has implications for cryptography based on the intractability of the IFP and DLP — including but not limited to for widely used schemes such as RSA, DSA and Diffie–Hellman. The algorithms in this thesis are all derived from, and make notable improvements to, the seminal works of Shor. Some of the contributions are joint works with other authors.
An algorithm of Ekerå and Gärtner, inspired by Regev’s factoring algorithm, computes discrete logarithms in multiplicative groups of prime fields. Asymptotically, it has the same qubit and gate complexity as Shor’s algorithm but splits the computation into d independent, parallel runs. The optimal value of this parameter is d∼n where n is the bit size of the cryptographic group. We propose an extension of this algorithm to hyperelliptic curves. For curves of genus g∼n, which are not used in cryptography, we prove unconditionally that the optimal number of parallel runs d∼n can still be achieved. For genus-two curves, we propose a heuristic algorithm. While its runtime speedup is difficult to quantify in general, we show that it can be expected to use up to d=8 parallel runs for specific curves relevant to cryptography, including GLV-friendly and pairing-friendly curves.