Paper 2020/1136 Original: eprint.iacr.org/2020/1136 ↗

A Note on Koblitz Curves over Prime Fields

Abstract

Besides the well-known class of Koblitz curves over binary fields, the class of Koblitz curves $E_b: y^2=x^3+b/\mathbb{F}_p$ over prime fields with $p\equiv 1 \pmod 3$ is also of some practical interest. By refining a classical result of Rajwade for the cardinality of $E_b(\mathbb{F}_p)$, we obtain a simple formula of $\#E_b(\mathbb{F}_p)$ in terms of the norm on the ring $\mathbb{Z}[\omega]$ of Eisenstein integers, that is, for some $\pi \in \mathbb{Z}[\omega]$ with $N(\pi)=p$ and some unit $u\in \mathbb{Z}[\omega]$, \[ \#E_b(\mathbb{F}_p)=N(\pi+u) \] holds. This establishes an interesting relation between the number of points on this class of curves and the number of elements of their underlying fields, they are given by the norm of two integers of $\mathbb{Z}[\omega]$ whose difference is just a unit. It is also interesting to note that such relationship has already been derived for the case of Koblitz curves over binary fields. Some tools that are useful in the computation of cubic residues are also developed.