Cryptology ePrint Archive: Report 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.

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:

[ Cryptology ePrint archive ]