Paper 2026/1244

Resource Estimation of the Distributed Quantum Algorithm for the Elliptic Curve Logarithm Problem

Abstract

Elliptic Curve Cryptography (ECC) underpins modern public-key infrastructure, relying on the computational hardness of the Elliptic Curve Discrete Logarithm Problem (ECDLP). While monolithic quantum computers running Shor's algorithm present a long-term threat to ECC, their physical realization is bottlenecked by the massive logical qubit demands of modular arithmetic—specifically modular inversion. Distributed Quantum Computing (DQC) offers a compelling alternative by linking smaller, cooperative quantum processing units (QPUs). In this paper, we adapt two distributed quantum algorithms to the elliptic curve setting and perform a rigorous resource estimation of their architectures. Integrating the compact, register-sharing Extended Euclidean Algorithm (EEA) formulation by Luo et al., we demonstrate distinct resource footprints for each approach on a cryptographically secure 256-bit elliptic curve. Specifically, Xu et al.'s zero-quantum-communication variant requires between 1080 and 1140 logical qubits per node (depending on the search window configuration), while Li et al.'s sequential quantum-communication-based variant can be realized with as few as 828 to 1068 logical qubits per node (depending on the number of participating network nodes). Our comparative analysis maps out the critical trade-offs between quantum communication overhead, classical coordination, and single-node hardware constraints, establishing a clear design space for near-term distributed quantum cryptanalysis.

Note: We added a new variant of the distributed quantum algorithm for ECDLP, along with its full analysis and resource estimation.