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

*Eisaku Furukawa and 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 $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$.

**Category / Keywords: **foundations / hyperelliptic curve cryptosystem, number theory

**Date: **received 25 Nov 2002, last revised 11 May 2003

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

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

**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 $y^2=x^5+a$.

**Version: **20030512:025444 (All versions of this report)

**Short URL: **ia.cr/2002/181

[ Cryptology ePrint archive ]