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

Eisaku Furukawa; Mitsuru Kawazoe; Tetsuya Takahashi

Paper 2002/181

Counting Points for Hyperelliptic Curves of type over Finite Prime Fields

Eisaku Furukawa, Mitsuru Kawazoe, and Tetsuya Takahashi

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 over given large prime fields , 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 where is a prime number greater than about and 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 where is not square in .

Note: The title has been changed. Titles of some sections have been changed. We added one subsection concerning the reducibility of the Jacobian varieties and one section concerning the algorithm for another curve .

Metadata

Available format(s): PDF PS
Category: Foundations
Publication info: Published elsewhere. Unknown where it was published
Keywords: hyperelliptic curve cryptosystem number theory
Contact author(s): kawazoe @ mi cias osakafu-u ac jp
History: 2003-05-12: last of 2 revisions; 2002-12-01: received; See all versions
Short URL: https://ia.cr/2002/181
License: CC BY

BibTeX

@misc{cryptoeprint:2002/181,
      author = {Eisaku Furukawa and Mitsuru Kawazoe and Tetsuya Takahashi},
      title = {Counting Points for Hyperelliptic Curves of type $y^2=x^5+ax$ over Finite Prime Fields},
      howpublished = {Cryptology {ePrint} Archive, Paper 2002/181},
      year = {2002},
      url = {https://eprint.iacr.org/2002/181}
}