An extension of Kedlaya's algorithm to Artin-Schreier curves in characteristic 2

J Denef, F Vercauteren

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

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 contributionAn extension of Kedlaya's algorithm to Artin-Schreier curves in characteristic 2
Original languageEnglish
Title of host publicationAlgorithmic Number Theory - ANTS 2002
EditorsClaus Fieker, David R. Kohel
PublisherSpringer Berlin Heidelberg
Pages369 - 384
Number of pages15
Volume2369
ISBN (Print)3540438637
Publication statusPublished - Jul 2002

Bibliographical note

Conference Proceedings/Title of Journal: Algorithmic Number Theory, 5th International Symposium, ANTS-V

Fingerprint Dive into the research topics of 'An extension of Kedlaya's algorithm to Artin-Schreier curves in characteristic 2'. Together they form a unique fingerprint.

Cite this