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

• URL: http://arxiv.org/abs/2607.13816v1
• Date: Wed, 15 Jul 2026 13:25:00 GMT
• Title: Quantum Algorithm for Elliptic Curve Discrete Logarithms with Space-Efficient Point Addition
• Abstract summary: 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.
• Score: 31.43193848243857
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 $919n^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 $195n^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.

Related papers

• A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
  We study tradeoff between solution quality and stability when elements arrive over time.<n>Our algorithm has a future implementation for rational oracle$ with $O(varepsilon-1)$ recourse and separate the existence of universal-price certificates from their efficient algorithms.
  arXiv  Detail & Related papers  (2026-09-09T10:13:43Z)
• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  A fundamental and long-standing challenge is their efficient approximation.<n>We develop a linear-space algorithm that requires $P(|hatboldsymbol-boldsymbol|_2geq)leq $ for all commonly used semi-values.<n>Our algorithm allows explicit minimization of the mean square error for each specific utility function.
  arXiv  Detail & Related papers  (2026-04-09T16:38:14Z)
• Space-Efficient Quantum Algorithm for Elliptic Curve Discrete Logarithms with Resource Estimation [30.009533492838028]
  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.
  arXiv  Detail & Related papers  (2026-04-02T17:52:00Z)
• End-to-End Efficient RL for Linear Bellman Complete MDPs with Deterministic Transitions [66.17960480460185]
  We study reinforcement learning with linear function approximation in Decision Processes (MDPs)<n>We provide a computationally efficient algorithm for linear Bellman complete oracles with emphdeterministic transitions, initial states, and rewards.
  arXiv  Detail & Related papers  (2026-03-24T17:32:29Z)
• Resource analysis of Shor's elliptic curve algorithm with an improved quantum adder on a two-dimensional lattice [7.999752490202695]
  Quantum computers have the potential to break classical cryptographic systems.<n>We propose a carry-lookahead quantum adder that achieves Toffoli depth $log n + loglog n + O(1)$ with only $O(n)$ ancillas.<n>We perform a comprehensive resource analysis of Shor's elliptic curve algorithm on two-dimensional lattices.
  arXiv  Detail & Related papers  (2025-10-27T11:02:10Z)
• 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)
• Second-order Conditional Gradient Sliding [70.88478428882871]
  We present the emphSecond-Order Conditional Gradient Sliding (SOCGS) algorithm.<n>The SOCGS algorithm converges quadratically in primal gap after a finite number of linearly convergent iterations.<n>It is useful when the feasible region can only be accessed efficiently through a linear optimization oracle.
  arXiv  Detail & Related papers  (2020-02-20T17:52:18Z)
• 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.