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

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⌊ log₂ n ⌋+O(1) logical qubits and 1056n³/log₂ n+O(n²) 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⌊ log₂ n ⌋+O(1) logical qubits and 229n²+O(nlog₂ 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.

Computing 256-bit elliptic curve discrete logarithms in 26 days on a fault-tolerant trapped-ion quantum computer with 20,000 qubits
Thomas Häner, Felix Tripier, Jacob Young +11
arXiv4 Sep 2026PreprintCC BY-NC-ND 4.0Full textQuantum physics & quantum informationarXiv
ECDSA.Fail: Open Autoresearch for Optimizing Elliptic-Curve Point Addition in Shor's Algorithm
Jieyi Long, Theodore Pender, Zhao Huang +32
arXiv19 Sep 2026PreprintCC BY 4.0Full textQuantum physics & quantum informationarXiv
Efficient Record-and-Replay Arithmetic for Quantum Elliptic-Curve Point Addition
Jieyi Long, Theodore Pender, Zhao Huang +33
arXiv24 Sep 2026PreprintCC BY 4.0Full textQuantum physics & quantum informationarXiv
Toward Efficient End-to-End Quantum Elliptic PDE Solvers: a Multilevel Correction Algorithm for Direct Observable Estimation
Xiantao Li
arXiv22 Sep 2026PreprintarXiv licenceFull textQuantum physics & quantum informationarXiv
An Efficient Quantum Spectral-Galerkin Method for Linear Elliptic Equations
Dongjie Wang, Sheng Chen
arXiv22 Oct 2026PreprintarXiv licenceFull textComputational physicsarXiv

Cite

BibTeX RIS

BibTeX

@misc{luo2026quantum,
  title = {{Quantum Algorithm for Elliptic Curve Discrete Logarithms with Space-Efficient Point Addition}},
  author = {Han Luo and Ziyi Yang and Jingquan Luo and Ziruo Wang and Yuexin Su and Xiaoming Sun and Lvzhou Li and Tongyang Li},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2607.13816},
  eprint = {2607.13816},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2607.13816},
}

RIS

TY  - UNPB
TI  - Quantum Algorithm for Elliptic Curve Discrete Logarithms with Space-Efficient Point Addition
AU  - Han Luo
AU  - Ziyi Yang
AU  - Jingquan Luo
AU  - Ziruo Wang
AU  - Yuexin Su
AU  - Xiaoming Sun
AU  - Lvzhou Li
AU  - Tongyang Li
PY  - 2026
DA  - 2026/09/05
PB  - arXiv
DO  - 10.48550/arxiv.2607.13816
UR  - https://arxiv.org/abs/2607.13816
AB  - 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_2 n ⌋+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⌊ log_2 n ⌋+O(1) logical qubits and 229n^2+O(nlog_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.
ER  -

Abstract

Related

Cite