**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.

**Category / Keywords: **public-key cryptography / public-key cryptography, complexity theory

**Date: **received 13 Mar 2021

**Contact author: **youri at math bas bg, miro@math bas bg

**Available format(s): **PDF | BibTeX Citation

**Version: **20210314:150750 (All versions of this report)

**Short URL: **ia.cr/2021/332

[ Cryptology ePrint archive ]