Short arithmetic terms express the cardinality of elliptic curves in Weierstraß normal form over finite fields

Source abstract

Arithmetic terms are fixed finite compositions of additions, multiplications, subtractions, divisions with remainder and integer exponentiations. An arithmetic term in natural numbers $A$, $B$, $n$, obtained by refining the general method of the second author (arXiv:2608.22049) for elliptic curves in Weierstraß normal form, counts the solutions in $(\mathbb Z/n\mathbb Z)^2$ for every modulus $n \geq 1$, with intermediate integers of approximately $2n^5$ binary digits instead of approximately $2n^{11}$. For a prime modulus $p \geq 17$, a second construction, based on the Hasse invariant and on the trace of Frobenius, gives a term of about thirty operations, in place of the fifty-one products of generalized geometric progressions of the general method.