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

• URL: http://arxiv.org/abs/2604.02311v1
• Date: Thu, 02 Apr 2026 17:52:00 GMT
• Title: Space-Efficient Quantum Algorithm for Elliptic Curve Discrete Logarithms with Resource Estimation
• Abstract summary: Elliptic Curve Discrete Logarithm Problem (ECDLP) is critical for evaluating the quantum security of widely deployed elliptic-curve cryptosystems.<n>We propose a space-efficient modular inversion algorithm for the ECDLP.<n>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 Hner et al.
• Score: 30.009533492838028
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Quantum Algorithm for Elliptic Curve Discrete Logarithms with Space-Efficient Point Addition [31.43193848243857]
  Elliptic Curve Discrete Logarithm Problem (ECDLP) is a fundamental problem in cryptography.<n>We present a space-efficient algorithm for solving ECDLP over prime fields, achieving an implementation with only $3n+6lfloor log nrfloor+O(1)$ logical qubits and $919n3/log n+O(n2)$ Toffoli gates.<n>Key to our improvement is a new space-efficient reversible modular inversion circuit, which addresses the dominant space bottleneck in affine-coordinate point addition.
  arXiv  Detail & Related papers  (2026-07-15T13:25:00Z)
• Improved quantum circuits for division [42.76841620787673]
  We develop new fault-tolerant quantum circuits for various integer division algorithms.<n> circuits achieve an up to 76.08% and 68.35% reduction in T-count and CNOT-count.
  arXiv  Detail & Related papers  (2026-03-18T13:41:43Z)
• Asymptotically Optimal Quantum Circuits for Comparators and Incrementers [2.488003578430483]
  We present quantum circuits for comparison and increment operations that achieve anally optimal gate count of $(n)$ and depth of $(log n)$ over the Clifford+Toffoli gate set.<n>We extend these results to classical-quantum comparators, yielding an improved classical-quantum adder with an optimal qubit count.
  arXiv  Detail & Related papers  (2026-03-13T11:41:14Z)
• Block encoding of sparse matrices with a periodic diagonal structure [67.45502291821956]
  We provide an explicit quantum circuit for block encoding a sparse matrix with a periodic diagonal structure.<n>Various applications for the presented methodology are discussed in the context of solving differential problems.
  arXiv  Detail & Related papers  (2026-02-11T07:24:33Z)
• Quantum and classical algorithms for SOCP based on the multiplicative weights update method [44.99833362998488]
  We give classical and quantum algorithms for approximately solving second-order cone programs (SOCPs)<n>Our approach follows the MW framework previously applied to semidefinite programs (SDPs)<n>We show that the additional structure of SOCPs can be exploited to give better runtime with SOCP-specific algorithms.
  arXiv  Detail & Related papers  (2025-07-18T17:55:58Z)
• Optimized circuits for windowed modular arithmetic with applications to quantum attacks against RSA [45.810803542748495]
  Windowed arithmetic is a technique for reducing the cost of quantum circuits with space--time tradeoffs.<n>In this work we introduce four optimizations to windowed modular exponentiation.<n>This leads to a $3%$ improvement in Toffoli count and Toffoli depth for modular exponentiation circuits relevant to cryptographic applications.
  arXiv  Detail & Related papers  (2025-02-24T16:59:16Z)
• On the Constant Depth Implementation of Pauli Exponentials [49.48516314472825]
  We decompose $Zotimes n$ exponentials of arbitrary length into circuits of constant depth using $mathcalO(n)$ ancillae and two-body XX and ZZ interactions.<n>We prove the correctness of our approach, after introducing novel rewrite rules for circuits which benefit from qubit recycling.
  arXiv  Detail & Related papers  (2024-08-15T17:09:08Z)
• Space-Efficient and Noise-Robust Quantum Factoring [10.974556218898435]
  Two improvements to Regev's recent quantum factoring algorithm.<n>Regev's circuit requires $O(n3/2)$ qubits and $O(n3/2 log n)$ gates.<n>Regev's analysis of his classical postprocessing procedure requires all $approx sqrtn$ runs to be successful.
  arXiv  Detail & Related papers  (2023-10-02T04:31:21Z)
• New Space-Efficient Quantum Algorithm for Binary Elliptic Curves using the Optimized Division Algorithm [1.2183405753834562]
  We suggest a new quantum division algorithm on the binary field which uses a smaller number of qubits. For elements in a field of $2n$, we can save $lceil n/2 rceil - 1$ qubits instead of using $8n2+4n-12+(16n-8)lfloorlog(n)rfloor$ more Toffoli gates.
  arXiv  Detail & Related papers  (2023-03-12T05:00:46Z)
• Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
  We consider learning in an adversarial Decision Process (MDP) where the loss functions can change arbitrarily over $K$ episodes. This paper provides two algorithms that improve the regret to $tildemathcal O(K2/3)$ in the same setting.
  arXiv  Detail & Related papers  (2023-01-30T14:37:21Z)
• Continuous Submodular Maximization: Beyond DR-Submodularity [48.04323002262095]
  We first prove a simple variant of the vanilla coordinate ascent, called Coordinate-Ascent+. We then propose Coordinate-Ascent++, that achieves tight $(1-1/e-varepsilon)$-approximation guarantee while performing the same number of iterations. The computation of each round of Coordinate-Ascent++ can be easily parallelized so that the computational cost per machine scales as $O(n/sqrtvarepsilon+nlog n)$.
  arXiv  Detail & Related papers  (2020-06-21T06:57:59Z)
• Improved quantum circuits for elliptic curve discrete logarithms [6.058525641792685]
  We present improved quantum circuits for elliptic curve scalar multiplication. We optimize low-level components such as reversible integer and modular arithmetic. We provide a full implementation of point addition in the Q# quantum programming language.
  arXiv  Detail & Related papers  (2020-01-27T04:08:49Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.