**Suitable Curves for Genus-4 HCC over Prime Fields: Point Counting Formulae for Hyperelliptic Curves of type $y^2=x^{2k+1}+ax$**

*Mitsuhiro Haneda and Mitsuru Kawazoe and Tetsuya Takahashi*

**Abstract: **Computing the order of the Jacobian group of a hyperelliptic curve
over a finite field is very important to construct
a hyperelliptic curve cryptosystem (HCC), because
to construct secure HCC, we need Jacobian groups of order in the form
$l¥cdot c$ where $l$ is a prime greater than about $2^{160}$ and
$c$ is a very small integer.
But even in the case of genus two,
known algorithms to compute the order of a Jacobian group for a general curve
need a very long running time over a large prime field.
In the case of genus three, only a few examples of suitable curves for HCC are known.
In the case of genus four, no example has been known over a large prime field.
In this article, we give explicit formulae of the order of Jacobian groups for
hyperelliptic curves over a finite prime field of type $y^2=x^{2k+1}+a x$,
which allows us to search suitable
curves for HCC. By using these formulae,
we can find many suitable curves for genus-4 HCC and show some examples.

**Category / Keywords: **public-key cryptography / hyperelliptic curve cryptosystem, number theory

**Date: **received 1 Jul 2004, last revised 15 Jul 2004

**Contact author: **kawazoe at mi cias osakafu-u ac jp

**Available format(s): **PDF | BibTeX Citation

**Note: **a minor error corrected.

**Version: **20040716:063408 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]