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

Yuri Borissov; Miroslav Markov

Paper 2021/332

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

Yuri Borissov

, Institute of Mathematics and Informatics, Bulgarian Academy of Sciences

Miroslav Markov

, Institute of Mathematics and Informatics, Bulgarian Academy of Sciences

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 $\tilde{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 almost an order of magnitude.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
Keywords: public-key cryptography complexity theory
Contact author(s): youri @ math bas bg
miro @ math bas bg
History: 2024-01-19: revised; 2021-03-14: received; See all versions
Short URL: https://ia.cr/2021/332
License: CC BY

BibTeX

@misc{cryptoeprint:2021/332,
      author = {Yuri Borissov and Miroslav Markov},
      title = {An $\tilde{O}(\log^2 p)$ Approach to Point-Counting on Elliptic Curves From a Prominent Family Over the Prime Field $\mathbb{F}_p$},
      howpublished = {Cryptology ePrint Archive, Paper 2021/332},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/332}},
      url = {https://eprint.iacr.org/2021/332}
}