**On the Family of Elliptic Curves $y^2=x^3+b/\mathbb{F}_p$**

*Han Wu and Guangwu Xu*

**Abstract: **This paper is devoted to a more precise classification of the family of curves $E_b:y^2=x^3+b/\mathbb{F}_p$.
For prime $p\equiv 1 \pmod 3$, explicit formula of the number of $\mathbb{F}_p$-rational points on $E_b$ is given
based on the the coefficients of a (primary) decomposition of $p=(c+d\omega)\overline{(c+d\omega)}$
in the ring $\mathbb{Z}[\omega]$ of Eisenstein integers. More specifically,
\[
\#E_b(\mathbb{F}_p)\in p+1-\big\{\pm(d-2c),\pm(c+d), \pm(c-2d)\big\}.
\]
The correspondence between these $6$ numbers of points and the $6$ isomorphism classes of the groups $E_b(\mathbb{F}_p)$
can be efficiently determined. Each of these numbers can also be interpreted as a norm of an Eisenstein integer.

For prime $p\equiv 2 \pmod 3$, it is known that $E_b(\mathbb{F}_p)\cong \mathbb{Z}_{p+1}$. Two efficiently computable isomorphisms are described within the single isomorphism class of groups for representatives $E_1(\mathbb{F}_p)$ and $E_{-3}(\mathbb{F}_p)$.

The explicit formulas $\#E_b(\mathbb{F}_p)$ for $p\equiv 1 \pmod 3$ are used in searching prime (or almost prime) order Koblitz curves over prime fields. An efficient procedure is described and analyzed. The procedure is proved to be deterministic polynomial time, assuming the Generalized Riemann Hypothesis. These formulas are also useful in using GLV method to perform fast scalar multiplications on the curve $E_b$.

Several tools that are useful in computing cubic residues are also developed in this paper.

**Category / Keywords: **public-key cryptography / Elliptic Curves, point counting, scalar multiplication, Eisenstein integers

**Date: **received 17 Sep 2020, last revised 9 Oct 2020

**Contact author: **gxu4sdq at sdu edu cn, gxu4uwm@uwm edu

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

**Version: **20201009:233009 (All versions of this report)

**Short URL: **ia.cr/2020/1136

[ Cryptology ePrint archive ]