Paper 2020/1136

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.