Paper 2020/1136

A Note on Koblitz Curves over Prime Fields

Han Wu
Guangwu Xu
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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Keywords
Elliptic Curvespoint countingEisenstein integers
Contact author(s)
hanwu97 @ mail sdu edu cn
gxu4sdq @ sdu edu cn
History
2023-02-20: last of 5 revisions
2020-09-21: received
See all versions
Short URL
https://ia.cr/2020/1136
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/1136,
      author = {Han Wu and Guangwu Xu},
      title = {A Note on Koblitz Curves over Prime Fields},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1136},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/1136}},
      url = {https://eprint.iacr.org/2020/1136}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.