Paper 2026/2725

Complete Addition Law for Twisted Edwards Curves

Abstract

We construct complete addition laws in extended coordinates for twisted Edwards curves \(E_{a,d}:ax^2+y^2=1+dx^2y^2\), where \(a,d\in K^\times\), \(a\ne d\), and \(\operatorname{char}K\ne2\). If \(t\in K\) makes \((t^2-a)(t^2-d)\) a nonzero nonsquare, the construction yields a \(K\)-complete formula valid for every pair of \(K\)-rational points. The proof describes the exceptional fibres through the difference morphism. Over finite fields of odd cardinality \(q>16\), such a coefficient exists for every nonsingular parameter pair, including the same-square-class cases with full rational two-torsion. We give full and mixed evaluation schedules. Full addition costs \(8M+D_c\) in split elementary models and \(10M\) or \(12M\), plus fixed-constant costs, in the same-square-class cases. Doubling costs \(4M+4S+\min(D_a,D_d)\), independently of coefficient selection. Here \(M\) denotes a general field multiplication, \(S\) a squaring, and \(D_c\) multiplication by a fixed \(c\in K\).