Paper 2026/2724

Complete Addition on Short Weierstrass Curves with Point-Free Lines

Abstract

Let $E_{a,b}:Y^2Z=X^3+aXZ^2+bZ^3$ be a nonsingular short-Weierstrass curve over a field $K$ of characteristic different from $2$ and $3$. A nonvertical line $Y=mX+nZ$ has no $K$-rational point on the curve if and only if $x^3-m^2x^2+(a-2mn)x+b-n^2$ is rootless in $K$. We give coordinate changes and formulas for the corresponding $K$-complete Bosma--Lenstra addition law. An incidence count proves that such a line exists over every finite field in the stated characteristic. The classical five-multiplication cross-product identity reduces the output computation by one multiplication. For normalized horizontal, sloped, and depressed families, the full/full costs are $13M+5D+30A$, $13M+5D+33A$, and $13M+(2\text{ to }5)D+60A$, respectively. Horizontal normalization requires a nonzero cube parameter; the depressed family always contains a point-free line over $\mathbb{F}_p$ for $p\ge47$. The zero-line formula costs $11M+3D_a+2D_{3b}+28A$ and is complete over finite $K$ exactly when $\#E(K)$ is odd. We also give complete doubling formulas, account for changes of coordinates, and apply the five-product identity to published Hessian addition formulas.