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

Quantum Information and Computation

Base of exponent representation matters -- more efficient reduction of discrete logarithm problem and elliptic curve discrete logarithm problem to the QUBO problem

Michał Wroński, Łukasz Dzierzkowski

Published Jun 1, 2024• 2 citations
Publisher

Abstract

This paper presents further improvements in the transformation of the Discrete Logarithm Problem (DLP) and Elliptic Curve Discrete Logarithm Problem (ECDLP) over prime fields to the Quadratic Unconstrained Binary Optimization (QUBO) problem. This is significant from a cryptanalysis standpoint, as QUBO problems may be solved using quantum annealers, and the fewer variables the resulting QUBO problem has, the less time is expected to obtain a solution.The main idea presented in the paper is allowing the representation of the exponent in different bases than the typically used base 2 (binary representation). It is shown that in such cases, the reduction of the discrete logarithm problem over the prime field \(\mathbb{F}_p\) to the QUBO problem may be obtained using approximately \(1.89n^2\) logical variables for \(n\) being the bitlength of prime \(p\), instead of the \(2n^2\) which was previously the best-known reduction method. The paper provides a practical example using the given method to solve the discrete logarithm problem over the prime field \(\mathbb{F}_{47}\). Similarly, for the elliptic curve discrete logarithm problem over the prime field \(\mathbb{F}_p\), allowing the representation of the exponent in different bases than typically used base two results in a lower number of required logical variables for \(n\) being the bitlength of prime \(p\), from \(3n^3\) to \(\frac{6n^3}{\log_{2}\left(\frac{3}{4}n\right)}\) logical variables, in the case of Edwards curves.

DOI
10.26421/qic24.7-8-1

Related papers

Transformation of Elliptic Curve Discrete Logarithm Problem to QUBO Using Direct Method in Quantum Annealing Applications

Michał Wroński, Elżbieta Burek, Łukasz Dzierzkowski +1 more

This paper investigates how to reduce the elliptic curve discrete logarithm problem over prime fields to the quadratic unconstrained binary optimization (QUBO) problem in order to obtain as few logical qubits as possible. In the best case scenario, if n is the bitlength of a characteristic of prime field Fp, approximately 3n³ logical qubits are required for such a reduction in the Edwards curve case. We present a practical attack on an elliptic curve discrete logarithm problem over the 3-bit prime field F7 for an elliptic curve with the subgroup of order 8. We solved this problem using the D-Wave Advantage QPU. To the best of the authors' knowledge, no one has made, so far, a practical attack on the elliptic curve discrete logarithm over a prime field using the direct quantum method.

Journal of Telecommunications and Information Technology•Feb 21, 2024•3 citations

The generalized method of solving ECDLP using quantum annealing

Łukasz Dzierzkowski

This paper presents a generalization of a method allowing the transformation of the Elliptic Curve Discrete Logarithm Problem (ECDLP) over prime fields to the Quadratic Unconstrained Binary Optimization (QUBO) problem. The original method requires that a given elliptic curve model has complete arithmetic. The new one has no such restriction, which is a breakthrough. Since the mentioned obstacle is no longer a problem, the latest version of the algorithm may be used for any elliptic curve model. As a result, one may use quantum annealing to solve ECDLP on any given model of elliptic curves.

International Journal of Electronics and Telecommunications•Apr 7, 2025•1 citation

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

The generalized method of solving ECDLP using quantum annealing

Łukasz Dzierzkowski

This paper presents a generalization of a method allowing the transformation of the Elliptic Curve Discrete Logarithm Problem (ECDLP) over prime fields to the Quadratic Unconstrained Binary Optimization (QUBO) problem. The original method requires that a given elliptic curve model has complete arithmetic. The new one has no such restriction, which is a breakthrough. Since the mentioned obstacle is no longer a problem, the latest version of the algorithm may be used for any elliptic curve model. As a result, one may use quantum annealing to solve ECDLP on any given model of elliptic curves.

arXiv:2410.08725•Oct 11, 2024•1 citation

Space-Efficient Quantum Algorithm for Elliptic Curve Discrete Logarithms with Resource Estimation

Han Luo, Ziyi Yang, Ziruo Wang +2 more

Solving the Elliptic Curve Discrete Logarithm Problem (ECDLP) is critical for evaluating the quantum security of widely deployed elliptic-curve cryptosystems. Consequently, minimizing the number of logical qubits required to execute this algorithm is a key object. In implementations of Shor's algorithm, the space complexity is largely dictated by the modular inversion operation during point addition. Starting from the extended Euclidean algorithm (EEA), we refine the register-sharing method of Proos and Zalka and propose a space-efficient reversible modular inversion algorithm. We use length registers together with location-controlled arithmetic to store the intermediate variables in a compact form throughout the computation. We then optimize the stepwise update rules and give concrete circuit constructions for the resulting controlled arithmetic components. This leads to a modular inversion circuit that uses $3n + 4\lfloor \log_2 n \rfloor + O(1)$ logical qubits and $204n^2\log_2 n + O(n^2)$ Toffoli gates. By inserting this modular inversion component into the controlled affine point-addition circuit, we obtain a space-efficient algorithm for the ECDLP with $5n + 4\lfloor \log_2 n \rfloor + O(1)$ qubits and $O(n^3)$ Toffoli gates. In particular, for a 256-bit prime-field curve, our estimate reduces the logical-qubit count to 1333, compared with 2124 in the previous low-width implementation of Häner et al.

quant-pharXiv:2604.02311•Apr 3, 2026•0 citations

Transformation of the discrete logarithm problem over $\mathbb F_{2^n}$ to the QUBO problem using normal bases

Michał Wroński, Mateusz Leśniak

Quantum computations are very important branch of modern cryptology. According to the number of working physical qubits available in general-purpose quantum computers and in quantum annealers, there is no coincidence, that nowadays quantum annealers allow to solve larger problems. In this paper we focus on solving discrete logarithm problem (DLP) over binary fields using quantum annealing. It is worth to note, that however solving DLP over prime fields using quantum annealing has been considered before, no author, until now, has considered DLP over binary fields using quantum annealing. Therefore, in this paper, we aim to bridge this gap. We present a polynomial transformation of the discrete logarithm problem over binary fields to the Quadratic Unconstrained Binary Optimization (QUBO) problem, using approximately $3n^2$ logical variables for the binary field $\mathbb{F}_{2^n}$. In our estimations, we assume the existence of an optimal normal base of II type in the given fields. Such a QUBO instance can then be solved using quantum annealing.

arXiv:2409.18534•Sep 27, 2024•0 citations
This paper presents further improvements in the transformation of the Discrete Logarithm Problem (DLP) and Elliptic Curve Discrete Logarithm Problem (ECDLP) over prime fields to the Quadratic Unconstrained Binary Optimization (QUBO) problem. This is significant from a cryptanalysis standpoint, as QUBO problems may be solved using quantum annealers, and the fewer variables the resulting QUBO problem has, the less time is expected to obtain a solution.The main idea presented in the paper is allowing the representation of the exponent in different bases than the typically used base 2 (binary representation). It is shown that in such cases, the reduction of the discrete logarithm problem over the prime field (\mathbb{F}p) to the QUBO problem may be obtained using approximately (1.89n^2) logical variables for (n) being the bitlength of prime (p), instead of the (2n^2) which was previously the best-known reduction method. The paper provides a practical example using the given method to solve the discrete logarithm problem over the prime field (\mathbb{F}{47}). Similarly, for the elliptic curve discrete logarithm problem over the prime field (\mathbb{F}p), allowing the representation of the exponent in different bases than typically used base two results in a lower number of required logical variables for (n) being the bitlength of prime (p), from (3n^3) to (\frac{6n^3}{\log{2}\left(\frac{3}{4}n\right)}) logical variables, in the case of Edwards curves.
This paper investigates how to reduce the elliptic curve discrete logarithm problem over prime fields to the quadratic unconstrained binary optimization (QUBO) problem in order to obtain as few logical qubits as possible. In the best case scenario, if n is the bitlength of a characteristic of prime field Fp, approximately 3n³ logical qubits are required for such a reduction in the Edwards curve case. We present a practical attack on an elliptic curve discrete logarithm problem over the 3-bit prime field F7 for an elliptic curve with the subgroup of order 8. We solved this problem using the D-Wave Advantage QPU. To the best of the authors' knowledge, no one has made, so far, a practical attack on the elliptic curve discrete logarithm over a prime field using the direct quantum method.
This paper presents a generalization of a method allowing the transformation of the Elliptic Curve Discrete Logarithm Problem (ECDLP) over prime fields to the Quadratic Unconstrained Binary Optimization (QUBO) problem. The original method requires that a given elliptic curve model has complete arithmetic. The new one has no such restriction, which is a breakthrough. Since the mentioned obstacle is no longer a problem, the latest version of the algorithm may be used for any elliptic curve model. As a result, one may use quantum annealing to solve ECDLP on any given model of elliptic curves.
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.
This paper presents a generalization of a method allowing the transformation of the Elliptic Curve Discrete Logarithm Problem (ECDLP) over prime fields to the Quadratic Unconstrained Binary Optimization (QUBO) problem. The original method requires that a given elliptic curve model has complete arithmetic. The new one has no such restriction, which is a breakthrough. Since the mentioned obstacle is no longer a problem, the latest version of the algorithm may be used for any elliptic curve model. As a result, one may use quantum annealing to solve ECDLP on any given model of elliptic curves.
Solving the Elliptic Curve Discrete Logarithm Problem (ECDLP) is critical for evaluating the quantum security of widely deployed elliptic-curve cryptosystems. Consequently, minimizing the number of logical qubits required to execute this algorithm is a key object. In implementations of Shor's algorithm, the space complexity is largely dictated by the modular inversion operation during point addition. Starting from the extended Euclidean algorithm (EEA), we refine the register-sharing method of Proos and Zalka and propose a space-efficient reversible modular inversion algorithm. We use length registers together with location-controlled arithmetic to store the intermediate variables in a compact form throughout the computation. We then optimize the stepwise update rules and give concrete circuit constructions for the resulting controlled arithmetic components. This leads to a modular inversion circuit that uses 3n+4⌊log⁡2n⌋+O(1)3n + 4\lfloor \log_2 n \rfloor + O(1)3n+4⌊log2​n⌋+O(1) logical qubits and 204n2log⁡2n+O(n2)204n^2\log_2 n + O(n^2)204n2log2​n+O(n2) Toffoli gates. By inserting this modular inversion component into the controlled affine point-addition circuit, we obtain a space-efficient algorithm for the ECDLP with 5n+4⌊log⁡2n⌋+O(1)5n + 4\lfloor \log_2 n \rfloor + O(1)5n+4⌊log2​n⌋+O(1) qubits and O(n3)O(n^3)O(n3) Toffoli gates. In particular, for a 256-bit prime-field curve, our estimate reduces the logical-qubit count to 1333, compared with 2124 in the previous low-width implementation of Häner et al.
Transformation of the discrete logarithm problem over F2n\mathbb F_{2^n}F2n​ to the QUBO problem using normal bases
Quantum computations are very important branch of modern cryptology. According to the number of working physical qubits available in general-purpose quantum computers and in quantum annealers, there is no coincidence, that nowadays quantum annealers allow to solve larger problems. In this paper we focus on solving discrete logarithm problem (DLP) over binary fields using quantum annealing. It is worth to note, that however solving DLP over prime fields using quantum annealing has been considered before, no author, until now, has considered DLP over binary fields using quantum annealing. Therefore, in this paper, we aim to bridge this gap. We present a polynomial transformation of the discrete logarithm problem over binary fields to the Quadratic Unconstrained Binary Optimization (QUBO) problem, using approximately 3n23n^23n2 logical variables for the binary field F2n\mathbb{F}_{2^n}F2n​. In our estimations, we assume the existence of an optimal normal base of II type in the given fields. Such a QUBO instance can then be solved using quantum annealing.