Space-Efficient Quantum Algorithm for Elliptic Curve Discrete Logarithms with Resource Estimation
Organizers：
刘正伟、刘子文、刘锦鹏、程嵩
Speaker：
Tongyang Li 李彤阳
(Peking University)
Time：
Fri., 14:00-15:00, May 29, 2026
Venue：
B626, Shuangqing Complex Building A
Online：
Tencent meeting: 230-432-7880
Password: BIMSA
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.
