SafetyPage

Research papers · Paper

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

Han Luo, Ziyi Yang, Jingquan Luo, Ziruo Wang, Yuexin Su, Xiaoming Sun, Lvzhou Li, Tongyang Li · 5 Sep 2026

Read at arxiv.org ↗Read at sourcearXiv non-exclusive licence

Outline · 50 pages

  1. Introductionp. 2
  2. Contributionsp. 3
  3. Overviewp. 4
  4. Open questionsp. 7
  5. Preliminariesp. 8
  6. Quantum computing and the Toffoli countsp. 8
  7. Elliptic curves and the ECDLPp. 9
  8. Shor's quantum algorithm for ECDLPp. 9
  9. Space-Efficient Extended Euclidean Algorithmp. 10
  10. The four-phase algorithm frameworkp. 11
  11. Space-efficient algorithm by register sharingp. 12
  12. Algorithmic optimizationsp. 15
  13. Quantum Circuit Implementation of Modular Inversionp. 18
  14. Overall circuit implementation of one stepp. 20
  15. Step-dependent active windowsp. 20
  16. Unary iterationp. 22
  17. Location-controlled operationsp. 23
  18. Affine Point Addition with Mid-Circuit Measurementp. 30
  19. Resource Estimation and the ECDLPp. 31
  20. Space complexity improvementsp. 32
  21. Asymptotic gate countsp. 32
  22. Numerical experimentsp. 34
  23. Resource estimates for Shor's ECDLP circuitp. 36
  24. Proof Detailsp. 41
  25. Bounds on the total number of stepsp. 41
  26. Step-dependent active windowsp. 45
  27. Improved Modular Multiplication Circuitp. 49