International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Counting Points for Hyperelliptic Curves of type $y^2=x^5+ax$ over Finite Prime Fields

Authors:
Eisaku Furukawa
Mitsuru Kawazoe
Tetsuya Takahashi
Download:
URL: http://eprint.iacr.org/2002/181
Search ePrint
Search Google
Abstract: Counting rational points on Jacobian varieties of hyperelliptic curves over finite fields is very important for constructing hyperelliptic curve cryptosystems (HCC), but known algorithms for general curves over given large prime fields need very long running times. In this article, we propose an extremely fast point counting algorithm for hyperelliptic curves of type $y^2=x^5+ax$ over given large prime fields $\Fp$, e.g. 80-bit fields. For these curves, we also determine the necessary condition to be suitable for HCC, that is, to satisfy that the order of the Jacobian group is of the form $l\cdot c$ where $l$ is a prime number greater than about $2^{160}$ and $c$ is a very small integer. We show some examples of suitable curves for HCC obtained by using our algorithm. We also treat curves of type $y^2=x^5+a$ where $a$ is not square in $\Fp$.
BibTeX
@misc{eprint-2002-11704,
  title={Counting Points for Hyperelliptic Curves of type $y^2=x^5+ax$ over Finite Prime Fields},
  booktitle={IACR Eprint archive},
  keywords={foundations / hyperelliptic curve cryptosystem, number theory},
  url={http://eprint.iacr.org/2002/181},
  note={ kawazoe@mi.cias.osakafu-u.ac.jp 12184 received 25 Nov 2002, last revised 11 May 2003},
  author={Eisaku Furukawa and Mitsuru Kawazoe and Tetsuya Takahashi},
  year=2002
}