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:2503.23939 · IEEE Transactions on Quantum Engineering

Simulation of Shor Algorithm for Discrete Logarithm Problems With Comprehensive Pairs of Modulo $p$ and Order $q$

Kaito Kishi, Junpei Yamaguchi, Tetsuya Izu, Noboru Kunihiro

Published Jan 1, 2025• 1 citation
arXivHTMLPDF

Abstract

The discrete logarithm problem (DLP) over finite fields, commonly used in classical cryptography, has no known polynomial-time algorithm on classical computers. However, Shor has provided its polynomial-time algorithm on quantum computers. Nevertheless, there are only few examples simulating quantum circuits that operate on general pairs of modulo$p$and order$q$. In this paper, we constructed such quantum circuits and solved DLPs for all 1,860 possible pairs of$p$and$q$up to 32 qubits using a quantum simulator with PRIMEHPC FX700. From this, we obtained and verified values of the success probabilities, which had previously been heuristically analyzed by [Ekerå, arXiv:1905.09084 (2019)]. As a result, the detailed waveform shape of the success probability of Shor's algorithm for solving the DLP, known as a periodic function of order$q$, was clarified. Additionally, we generated 1,015 quantum circuits for larger pairs of$p$and$q$, extrapolated the circuit sizes obtained, and compared them for$p = 2048$bits between safeprime groups and Schnorr groups. While in classical cryptography, the cipher strength of safe-prime groups and Schnorr groups is the same if$p$is equal, we quantitatively demonstrated how much the strength of the latter decreases to the bit length of$p$in the former when using Shor's quantum algorithm. In particular, it was experimentally and theoretically shown that when a basic adder is used in the addition circuit, the cryptographic strength of a Schnorr group with$p = 2048$bits under Shor's algorithm is almost equivalent to that of a safe-prime group with$p = 1024$bits.

DOI
10.1109/tqe.2025.3591213

Related papers

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

The Present and Future of Discrete Logarithm Problems on Noisy Quantum Computers

Yoshinori Aono, Sitong Liu, Tomoki Tanaka +4 more

The discrete logarithm problem (DLP) is the basis for several cryptographic primitives. Since Shor’s work, it has been known that the DLP can be solved by combining a polynomial-size quantum circuit and a polynomial-time classical post-processing algorithm. The theoretical result corresponds the situation where a quantum device working with a medium number of qubits of very small errors can solve DLP. However, all the quantum devices that we can use have a limited number of noisy qubits, as of the noisy intermediate-scale quantum (NISQ) era. Thus, evaluating the instance size that the latest quantum device can solve, and give a future prediction of the size along the progress of quantum devices are emerging research topics. This paper contains two proposal to discuss the performance of quantum devices against DLP in the NISQ era. (1) A quantitative measure based on the success probability of the post-processing algorithm to determine whether an experiment on a quantum device (or a classical simulator) succeeded. (2) A procedure to modify bit strings observed from a Shor’s circuit to increase the success probability of a lattice-based post-processing algorithm. We conducted our experiments with theibm_kawasakidevice and discovered that the simplest circuit (7 qubits) from a 2-bit DLP instance achieves a sufficiently high success probability to proclaim the experiment successful. Experiments on another circuit from a slightly harder 2-bit DLP instance, on the other hand, did not succeed, and we determined that reducing the noise level by half is required to achieve a successful experiment. Finally, we give a near-term prediction based on required noise levels to solve some selected small DLP and integer factoring instances.

arXiv:2111.06102•IEEE Transactions on Quantum Engineering•Jan 1, 2022•11 citations

Revisiting Shor's quantum algorithm for computing general discrete logarithms

Martin Ekerå

We heuristically show that Shor's algorithm for computing general discrete logarithms achieves an expected success probability of approximately 60% to 82% in a single run when modified to enable efficient implementation with the semi-classical Fourier transform. By slightly increasing the number of group operations that are evaluated quantumly and performing a single limited search in the classical post-processing, or by performing two limited searches in the post-processing, we show how the algorithm can be further modified to achieve a success probability that heuristically exceeds 99% in a single run. We provide concrete heuristic estimates of the success probability of the modified algorithm, as a function of the group order $r$, the size of the search space in the classical post-processing, and the additional number of group operations evaluated quantumly. In the limit as $r \rightarrow \infty$, we heuristically show that the success probability tends to one. In analogy with our earlier works, we show how the modified quantum algorithm may be heuristically simulated classically when the logarithm $d$ and $r$ are both known. Furthermore, we heuristically show how slightly better tradeoffs may be achieved, compared to our earlier works, if $r$ is known when computing $d$. We generalize our heuristic to cover some of our earlier works, and compare it to the non-heuristic analyses in those works.

arXiv:1905.09084•May 22, 2019•9 citations

Quantum algorithm for solving binary hyperelliptic curve discrete logarithm problem

Yan Huang, Du Zeng, Chao Chen +2 more

Abstract It is well-established that Shor’s algorithm can solve the discrete logarithm problem (DLP) in polynomial time. The hyperelliptic curve DLP (HCDLP) of genus 2 has found widespread industrial applications and remains an active research domain. In this work, we develop a quantum algorithm for solving HCDLP over binary fields $$\mathbb {F}_{2^n}$$ F 2 n by adapting Shor’s algorithmic framework. The core innovation lies in our divisor addition implementation, which combines the geometric interpretation of divisor operations with symmetric polynomial techniques. Using representative parameters ( $$n = 163, 283, 571$$ n = 163 , 283 , 571 ), we quantify the required quantum resources from the perspective of minimal qubit count, minimal T-gate usage, and minimal quantum depth. Furthermore, we compare the quantum resources required for solving HCDLP over binary fields with those for solving HCDLP over general prime fields and demonstrate the vulnerability of HCDLP-based cryptosystems to quantum attacks. Our analysis reveals that: (1) solving HCDLP over binary fields requires fewer quantum gates and less quantum depth compared to solving it over general prime fields; (2) the maximum achievable quantum depth for HCDLP attacks falls below NIST’s minimum security threshold of $$2^{40}$$ 2 40 for comparable protection levels, and (3) the quantum computational cost is orders of magnitude lower than the $$2^{157}$$ 2 157 resources needed for AES-128 attacks.

Cybersecurity•Dec 17, 2025•0 citations

Quantum Algorithm for Elliptic Curve Discrete Logarithms with Space-Efficient Point Addition

Han Luo, Ziyi Yang, Jingquan Luo +5 more

The Elliptic Curve Discrete Logarithm Problem (ECDLP) is a fundamental problem in cryptography, and reducing the resource requirements of quantum algorithms for solving ECDLP is an important goal. In this work, we present a space-efficient quantum algorithm for solving the ECDLP over prime fields, achieving an implementation with only $3n+6\lfloor \log_2 n \rfloor+O(1)$ logical qubits and $1056n^3/\log_2 n+O(n^2)$ Toffoli gates, where $n$ is the bit-length of the prime. For a 256-bit prime-field curve, our construction requires only 835 logical qubits, reducing the previous best estimates of 1098 and 1175 logical qubits by Chevignard et al. [EUROCRYPT 2026] and Babbush et al. [ArXiv Preprint 2026], respectively. The key to our improvement is a new space-efficient reversible modular inversion circuit, which addresses the dominant space bottleneck in affine-coordinate point addition. Starting from the extended Euclidean algorithm (EEA), we refine the register-sharing technique of Proos and Zalka by introducing length registers and location-controlled arithmetic to compactly store and update intermediate variables. We further optimize the reversible update procedures and construct the corresponding controlled arithmetic circuits, resulting in a modular inversion circuit implemented by only $2n+6\lfloor \log_2 n \rfloor+O(1)$ logical qubits and $229n^2+O(n\log_2 n)$ Toffoli gates. This modular inversion circuit together with mid-circuit measurements and classical feed-forward operations provides a space-efficient controlled affine point-addition circuit and a complete implementation of Shor's algorithm for ECDLP.

quant-pharXiv:2607.13816•Jul 16, 2026•0 citations

Variational Quantum Algorithm for Solving Discrete Logarithms

RONG Xiaojun ZHANG Xinglan

The discrete logarithm problem is a significant challenge in number theory,and due to the difficulty of solving it,classical computers lack efficient algorithms for this task.As a result,the discrete logarithm problem is widely used in public key cryptosystems,and if it were cracked,it would pose a direct threat to the security of these systems.However,with the advent of quantum computing,researchers have begun exploring quantum computers as a potential solution for the discrete logarithm problem.Currently,most quantum algorithms for solving the discrete logarithm problem are based on Shor’s algorithm.However,due to Shor’s inherent limitations,these algorithms often face issues such as large quantum circuit depth,high qubit usage and complex post-processing steps.This makes it difficult for Shor’s algorithm to be implemented on NISQ computers.To address these issues,this paper proposes a novel approach by introducing a variational quantum algorithm for solving the discrete logarithm pro-blem.This algorithm leverages the parallelism of quantum computing to compute the modular exponentiation of parameterized quantum states.It also designs a marked solution circuit that maps valid solutions of the discrete logarithm problem onto auxiliary qubits.Then,a classical optimizer is used to iteratively adjust the parameters within the parameterized quantum circuit,continuously reducing the value of a designed loss function.Finally,the optimized parameters from the classical optimizer are fed into the measurement circuit,where the solution to the discrete logarithm problem can be obtained with high probability.Compared to Shor’s algorithm,the proposed method significantly reduces the required number of qubits and nearly halves the quantum circuit depth.Furthermore,this paper provides a detailed design of the quantum circuit and verifies the correctness of the proposed algorithm using the Qiskit package in Python.

•Jan 1, 2026•0 citations
Simulation of Shor Algorithm for Discrete Logarithm Problems With Comprehensive Pairs of Modulo ppp and Order qqq
The discrete logarithm problem (DLP) over finite fields, commonly used in classical cryptography, has no known polynomial-time algorithm on classical computers. However, Shor has provided its polynomial-time algorithm on quantum computers. Nevertheless, there are only few examples simulating quantum circuits that operate on general pairs of modulopppand orderqqq. In this paper, we constructed such quantum circuits and solved DLPs for all 1,860 possible pairs ofpppandqqqup to 32 qubits using a quantum simulator with PRIMEHPC FX700. From this, we obtained and verified values of the success probabilities, which had previously been heuristically analyzed by [Ekerå, arXiv:1905.09084 (2019)]. As a result, the detailed waveform shape of the success probability of Shor's algorithm for solving the DLP, known as a periodic function of orderqqq, was clarified. Additionally, we generated 1,015 quantum circuits for larger pairs ofpppandqqq, extrapolated the circuit sizes obtained, and compared them forp=2048p = 2048p=2048bits between safeprime groups and Schnorr groups. While in classical cryptography, the cipher strength of safe-prime groups and Schnorr groups is the same ifpppis equal, we quantitatively demonstrated how much the strength of the latter decreases to the bit length ofpppin the former when using Shor's quantum algorithm. In particular, it was experimentally and theoretically shown that when a basic adder is used in the addition circuit, the cryptographic strength of a Schnorr group withp=2048p = 2048p=2048bits under Shor's algorithm is almost equivalent to that of a safe-prime group withp=1024p = 1024p=1024bits.
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.
The discrete logarithm problem (DLP) is the basis for several cryptographic primitives. Since Shor’s work, it has been known that the DLP can be solved by combining a polynomial-size quantum circuit and a polynomial-time classical post-processing algorithm. The theoretical result corresponds the situation where a quantum device working with a medium number of qubits of very small errors can solve DLP. However, all the quantum devices that we can use have a limited number of noisy qubits, as of the noisy intermediate-scale quantum (NISQ) era. Thus, evaluating the instance size that the latest quantum device can solve, and give a future prediction of the size along the progress of quantum devices are emerging research topics. This paper contains two proposal to discuss the performance of quantum devices against DLP in the NISQ era. (1) A quantitative measure based on the success probability of the post-processing algorithm to determine whether an experiment on a quantum device (or a classical simulator) succeeded. (2) A procedure to modify bit strings observed from a Shor’s circuit to increase the success probability of a lattice-based post-processing algorithm. We conducted our experiments with theibm_kawasakidevice and discovered that the simplest circuit (7 qubits) from a 2-bit DLP instance achieves a sufficiently high success probability to proclaim the experiment successful. Experiments on another circuit from a slightly harder 2-bit DLP instance, on the other hand, did not succeed, and we determined that reducing the noise level by half is required to achieve a successful experiment. Finally, we give a near-term prediction based on required noise levels to solve some selected small DLP and integer factoring instances.
We heuristically show that Shor's algorithm for computing general discrete logarithms achieves an expected success probability of approximately 60% to 82% in a single run when modified to enable efficient implementation with the semi-classical Fourier transform. By slightly increasing the number of group operations that are evaluated quantumly and performing a single limited search in the classical post-processing, or by performing two limited searches in the post-processing, we show how the algorithm can be further modified to achieve a success probability that heuristically exceeds 99% in a single run. We provide concrete heuristic estimates of the success probability of the modified algorithm, as a function of the group order rrr, the size of the search space in the classical post-processing, and the additional number of group operations evaluated quantumly. In the limit as r→∞r \rightarrow \inftyr→∞, we heuristically show that the success probability tends to one. In analogy with our earlier works, we show how the modified quantum algorithm may be heuristically simulated classically when the logarithm ddd and rrr are both known. Furthermore, we heuristically show how slightly better tradeoffs may be achieved, compared to our earlier works, if rrr is known when computing ddd. We generalize our heuristic to cover some of our earlier works, and compare it to the non-heuristic analyses in those works.
Abstract It is well-established that Shor’s algorithm can solve the discrete logarithm problem (DLP) in polynomial time. The hyperelliptic curve DLP (HCDLP) of genus 2 has found widespread industrial applications and remains an active research domain. In this work, we develop a quantum algorithm for solving HCDLP over binary fields F2n\mathbb {F}_{2^n}F2n​ F 2 n by adapting Shor’s algorithmic framework. The core innovation lies in our divisor addition implementation, which combines the geometric interpretation of divisor operations with symmetric polynomial techniques. Using representative parameters ( n=163,283,571n = 163, 283, 571n=163,283,571 n = 163 , 283 , 571 ), we quantify the required quantum resources from the perspective of minimal qubit count, minimal T-gate usage, and minimal quantum depth. Furthermore, we compare the quantum resources required for solving HCDLP over binary fields with those for solving HCDLP over general prime fields and demonstrate the vulnerability of HCDLP-based cryptosystems to quantum attacks. Our analysis reveals that: (1) solving HCDLP over binary fields requires fewer quantum gates and less quantum depth compared to solving it over general prime fields; (2) the maximum achievable quantum depth for HCDLP attacks falls below NIST’s minimum security threshold of 2402^{40}240 2 40 for comparable protection levels, and (3) the quantum computational cost is orders of magnitude lower than the 21572^{157}2157 2 157 resources needed for AES-128 attacks.
The Elliptic Curve Discrete Logarithm Problem (ECDLP) is a fundamental problem in cryptography, and reducing the resource requirements of quantum algorithms for solving ECDLP is an important goal. In this work, we present a space-efficient quantum algorithm for solving the ECDLP over prime fields, achieving an implementation with only 3n+6⌊log⁡2n⌋+O(1)3n+6\lfloor \log_2 n \rfloor+O(1)3n+6⌊log2​n⌋+O(1) logical qubits and 1056n3/log⁡2n+O(n2)1056n^3/\log_2 n+O(n^2)1056n3/log2​n+O(n2) Toffoli gates, where nnn is the bit-length of the prime. For a 256-bit prime-field curve, our construction requires only 835 logical qubits, reducing the previous best estimates of 1098 and 1175 logical qubits by Chevignard et al. [EUROCRYPT 2026] and Babbush et al. [ArXiv Preprint 2026], respectively. The key to our improvement is a new space-efficient reversible modular inversion circuit, which addresses the dominant space bottleneck in affine-coordinate point addition. Starting from the extended Euclidean algorithm (EEA), we refine the register-sharing technique of Proos and Zalka by introducing length registers and location-controlled arithmetic to compactly store and update intermediate variables. We further optimize the reversible update procedures and construct the corresponding controlled arithmetic circuits, resulting in a modular inversion circuit implemented by only 2n+6⌊log⁡2n⌋+O(1)2n+6\lfloor \log_2 n \rfloor+O(1)2n+6⌊log2​n⌋+O(1) logical qubits and 229n2+O(nlog⁡2n)229n^2+O(n\log_2 n)229n2+O(nlog2​n) Toffoli gates. This modular inversion circuit together with mid-circuit measurements and classical feed-forward operations provides a space-efficient controlled affine point-addition circuit and a complete implementation of Shor's algorithm for ECDLP.
The discrete logarithm problem is a significant challenge in number theory,and due to the difficulty of solving it,classical computers lack efficient algorithms for this task.As a result,the discrete logarithm problem is widely used in public key cryptosystems,and if it were cracked,it would pose a direct threat to the security of these systems.However,with the advent of quantum computing,researchers have begun exploring quantum computers as a potential solution for the discrete logarithm problem.Currently,most quantum algorithms for solving the discrete logarithm problem are based on Shor’s algorithm.However,due to Shor’s inherent limitations,these algorithms often face issues such as large quantum circuit depth,high qubit usage and complex post-processing steps.This makes it difficult for Shor’s algorithm to be implemented on NISQ computers.To address these issues,this paper proposes a novel approach by introducing a variational quantum algorithm for solving the discrete logarithm pro-blem.This algorithm leverages the parallelism of quantum computing to compute the modular exponentiation of parameterized quantum states.It also designs a marked solution circuit that maps valid solutions of the discrete logarithm problem onto auxiliary qubits.Then,a classical optimizer is used to iteratively adjust the parameters within the parameterized quantum circuit,continuously reducing the value of a designed loss function.Finally,the optimized parameters from the classical optimizer are fed into the measurement circuit,where the solution to the discrete logarithm problem can be obtained with high probability.Compared to Shor’s algorithm,the proposed method significantly reduces the required number of qubits and nearly halves the quantum circuit depth.Furthermore,this paper provides a detailed design of the quantum circuit and verifies the correctness of the proposed algorithm using the Qiskit package in Python.