Resource Estimates for Quantum Discrete Logarithm Computations on 256-bit Elliptic Curves
Summarize this article with:
Resource Estimates for Quantum Discrete Logarithm Computations on 256-bit Elliptic Curves A technical paper by Clémence Chevignard, Pierre-Alain Fouque, and André Schrottenloher, scheduled for EUROCRYPT 2026, describes a method to solve the Discrete Logarithm problem on 256-bit elliptic curves (ECDLP) using 1,098 logical qubits. This is a reduction from previous estimates of 2,124 logical qubits for the same security level. The approach utilizes a space-optimized implementation of Shor’s algorithm that achieves a space complexity of 3.12n for an n-bit curve. This puts the qubit requirement for breaking 256-bit ECC below that of factoring 3072-bit RSA, which currently requires an estimated 2,043 logical qubits. The reduction in qubit count is achieved through output compression using a single-bit hash function based on the Legendre symbol. Instead of explicitly computing modular inversions to obtain unique affine coordinates—a process that typically requires substantial auxiliary qubit space—the algorithm calculates the Legendre symbol of the projective coordinates. This is supported by a Residue Number System (RNS) that decomposes large integer operations into smaller residues processed within a binary tree. This architecture replaces the standard coordinate conversion with a more space-efficient arithmetic pipeline, though it shifts the computational burden from memory to logic operations. While the method reduces the logical qubit threshold, it results in a higher gate count. The asymptotic complexity increases from cubic scaling to quartic scaling. For a 256-bit curve, the implementation requires approximately 238.10 Toffoli gates per run, a significant increase over the previous estimate of roughly 230. To maintain low auxiliary space, the team employed a spooky pebbling strategy, which uses measurement-based uncomputation to recycle qubits during the binary tree traversal. The researchers concluded that for early fault-tolerant systems where logical qubits are the primary bottleneck, this trade-off provides a viable path to executing cryptanalytic algorithms on smaller hardware configurations. For the full technical details on the RNS-based point multiplication and Legendre symbol compression, consult the paper on the IACR ePrint archive here. You may also view the commentary on these results from William Zeng of the Unitary Foundation here. March 26, 2026 Mohamed Abdel-Kareem2026-03-26T16:04:21-07:00 Leave A Comment Cancel replyComment Type in the text displayed above Δ This site uses Akismet to reduce spam. Learn how your comment data is processed.