An Efficient Approach to Point-Counting on Elliptic Curves from a Prominent Family over the Prime Field F_p

Abstract

Here, we elaborate an approach for determining the number of points on elliptic curves from the family \(\mathcal{E_p} = \{E_a : y^2 = x^3 + a \pmod{p}, a\not= 0\}\), where p is a prime number >3. The essence of this approach consists in combining the well-known Hasse bound with an explicit formula for the quantities of interest-reduced modulo \(p\). It allows to advance an efficient technique to compute the six cardinalities associated with the family \(\mathcal{E_p}\), for \(p\equiv 1 \pmod{3}\), whose complexity is \(\tilde{O}(log^2p)\), thus improving the best-known algorithmic solution with almost an order of magnitude.