研究探讨量子密码分析中的椭圆曲线算术：以Curve25519为例

Recent quantum resource estimates over prime fields have largely focused on prime order elliptic curves. We implement modern affine circuit techniques on the widely deployed composite order curve, Curve25519, and obtain a scalar circuit using 47,199,530 CCX gates and 1,189 peak logical qubits. This uses approximately 35% and 18% fewer gates than Schrottenloher's published space- and gate-optimized secp256k1 circuits, respectively. We separate three contributions. First, we apply established arithmetic and signed table techniques to Curve25519. In a comparison using the same arithmetic framework and signed half tables, its field and subgroup parameters, together with the chosen GCD iteration budgets, save 2,218,944 CCX gates relative to secp256k1. Second, we adapt odd signed digit recoding to quantum windows using fixed output translations. This saves a further 15,204 CCX gates and also applies to prime order curves. Third, we combine nonzero digits with a fixed 8-torsion offset point to keep the accumulator outside the lookup points' subgroup. With zero slope support and exact field arithmetic, this yields an exception-free addition schedule and nonzero denominators during slope uncomputation, without additional quantum point additions. Our counts include the full scalar schedule, lookup and cleanup. The corresponding implementation uses truncated arithmetic and heuristic GCD budgets, and excludes Fourier rotation synthesis and classical recovery.