Short arithmetic terms for the cardinality of elliptic curves over rings of remainder classes and over finite fields

Abstract

Arithmetic terms are fixed finite compositions of addition, truncated subtraction, multiplication, integer division and exponentiation on natural numbers. We construct such terms for the number of affine solutions of $y^2=x^3+Ax+B$. For arbitrary moduli $n\ge 1$, a specialization of Prunescu's general construction reduces the number of monomial contributions from fourty-nine to fifteen and the size of the packed integer from approximately $2n^{11}$ to approximately $2n^5$ binary digits. For prime moduli $p\ge 17$, the Hasse invariant and the trace of Frobenius give a term of about thirty operations. For curves defined over ${\mathbb{F}}_p$, a further term counts the points over ${\mathbb{F}}_{p^k}$ with $k$ as a variable. For primes $p\ge 5$, we also obtain arithmetic terms for the counts over $\mathbb{Z}/p^k\mathbb{Z}$ with $k$ variable, covering good reduction, nodes and cusps, including non-minimal equations and zero discriminant.