On the Family of Elliptic Curves y2 x3+b/픽p
This paper is devoted to a more precise classification of the family of curves Eb : y 2 = x3 + b/Fp. For prime p ≡ 1 (mod 3), explicit formula of the number of Fp-rational points on Eb is given based on the the coefficients of a (primary) decomposition of p = (c + dω)(c + dω) in the ring Z[ω] of Eisenstein integers. More specifically, #Eb(Fp) ∈ p + 1− { ± (d− 2c),±(c + d),±(c− 2d) } . The correspondence between these 6 numbers of points and the 6 isomorphism classes of the groups Eb(Fp) can be efficiently determined. Each of these numbers can also be interpreted as a norm of an Eisenstein integer. For prime p ≡ 2 (mod 3), it is known that Eb(Fp) ∼= Zp+1. Two efficiently computable isomorphisms are described within the single isomorphism class of groups for representatives E1(Fp) and E−3(Fp). The explicit formulas #Eb(Fp) for p ≡ 1 (mod 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 Eb. Several tools that are useful in computing cubic residues are also developed in this paper.