Paper 2026/2688

Elliptic Curve Arithmetic for Quantum Cryptanalysis: A Study of Curve25519

Abstract

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.