Paper 2021/332

An $O(\log^2 p)$ Approach to Point-Counting on Elliptic Curves From a Prominent Family Over the Prime Field $\mathbb{F}_p$

Yuri Borissov and Miroslav Markov

Abstract

We elaborate an approach for determining the order of an elliptic curve 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 that order reduced to modulo $p$. It allows to advance an efficient technique of complexity $O(\log^2 p)$ for computing simultaneously the six orders associated with the family $\mathcal{E}_p$ when $p \equiv 1 \pmod 3$, thus improving the best known algorithmic solution for that problem with an order of magnitude.