Abstract
In this paper we present an extension of Kedlaya's algorithm for computing the zeta function of an Artin-Schreier curve over a finite field $\FF_q$ of characteristic 2. The algorithm has running time $O(g^5 + arepsilon \log^3 + arepsilon q)$ and needs $O(g^3 \log^3 q)$ storage space for a genus $g$ curve. Our first implementation in M\small AGMA shows that one can now generate hyperelliptic curves suitable for cryptography in reasonable time. We also compare our algorithm with an algorithm by Lauder and Wan which has the same time and space complexity. Furthermore, the method introduced in this paper can be used for any hyperelliptic curve over a finite field of characteristic 2.
| Translated title of the contribution | An extension of Kedlaya's algorithm to Artin-Schreier curves in characteristic 2 |
|---|---|
| Original language | English |
| Title of host publication | Algorithmic Number Theory - ANTS 2002 |
| Editors | Claus Fieker, David R. Kohel |
| Publisher | Springer Berlin Heidelberg |
| Pages | 369 - 384 |
| Number of pages | 15 |
| Volume | 2369 |
| ISBN (Print) | 3540438637 |
| Publication status | Published - Jul 2002 |