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\lfloor {\log }_{2}n\rfloor +O(1)$ logical qubits and $1008n^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 $217n^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.

46 pages, 15 figures, 6 tables. This paper supersedes our earlier preprint arXiv:2604.02311. Compared with the earlier version, the present paper reduces the space complexity from $5n+O({\log }_{2}n)$ to $3n+O({\log }_{2}n)$ for affine point addition and from $3n+O({\log }_{2}n)$ to $2n+O({\log }_{2}n)$ for modular inversion

Topics & keywords