An extension of Kedlaya’s algorithm to Artin-Schreier curves in characteristic 2. (English) Zbl 1058.11040

Denef, Jan; Vercauteren, Frederik

Fieker, Claus (ed.) et al., Algorithmic number theory. 5th international symposium, ANTS-V, Sydney, Australia, July 7–12, 2002. Proceedings. Berlin: Springer (ISBN 3-540-43863-7). Lect. Notes Comput. Sci. 2369, 308-323 (2002).

Summary: 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 \(\mathbb {F}_{q}\) of characteristic 2. The algorithm has running time \(O(g^{5 + \varepsilon} \log^{3 + \varepsilon} q)\) and needs \(O(g^3 \log^3 q)\) storage space for a genus \(g\) curve. Our first implementation in MAGMA 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.
For the entire collection see [Zbl 0992.00024].

MSC:

11G20	Curves over finite and local fields
14G10	Zeta functions and related questions in algebraic geometry (e.g., Birch-Swinnerton-Dyer conjecture)
14G15	Finite ground fields in algebraic geometry
14G50	Applications to coding theory and cryptography of arithmetic geometry
11Y16	Number-theoretic algorithms; complexity

Keywords:

Hyperelliptic curves; Monsky-Washnitzer cohomology; Kedlaya’s algorithm; Lauder-Wan algorithm; cryptography