Computing zeta functions of hyperelliptic curves over finite fields of characteristic 2

F Vercauteren

Computing zeta functions of hyperelliptic curves over finite fields of characteristic 2

F Vercauteren

Cryptography and Information Security

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

17 Citations (Scopus)

Abstract

We present an algorithm for computing the zeta function of an arbitrary hyperelliptic curve over a finite field $\FF_q$ of characteristic 2, thereby extending the algorithm of Kedlaya for small odd characteristic. For a genus $g$ hyperelliptic curve over $\FF_2^n$, the asymptotic running time of the algorithm is $O(g^5 + arepsilon n^3 + arepsilon)$ and the space complexity is $O(g^4 n^3)$.

Translated title of the contribution	Computing zeta functions of hyperelliptic curves over finite fields of characteristic 2
Original language	English
Title of host publication	Advances in Cryptology -- CRYPTO 2002
Publisher	Springer Berlin Heidelberg
Pages	369 - 384
Number of pages	15
Volume	2442
Publication status	Published - Aug 2002

Bibliographical note

Editors: Moti Yung
Publisher: Springer

Access to Document

http://www.cs.bris.ac.uk/Publications/pub_info.jsp?id=1000652

Handle.net

Persistent link

Cite this

@inproceedings{cf0588ba85ff4c0a9b139d98c3199443,

title = "Computing zeta functions of hyperelliptic curves over finite fields of characteristic 2",

abstract = "We present an algorithm for computing the zeta function of an arbitrary hyperelliptic curve over a finite field \$\textbackslash{}FF\_q\$ of characteristic 2, thereby extending the algorithm of Kedlaya for small odd characteristic. For a genus \$g\$ hyperelliptic curve over \$\textbackslash{}FF\_2\textasciicircum{}n\$, the asymptotic running time of the algorithm is \$O(g\textasciicircum{}5 + arepsilon n\textasciicircum{}3 + arepsilon)\$ and the space complexity is \$O(g\textasciicircum{}4 n\textasciicircum{}3)\$. ",

author = "F Vercauteren",

note = "Editors: Moti Yung Publisher: Springer",

year = "2002",

month = aug,

language = "English",

volume = "2442",

pages = "369 -- 384",

booktitle = "Advances in Cryptology -- CRYPTO 2002",

publisher = "Springer Berlin Heidelberg",

address = "Germany",

}

TY - GEN

T1 - Computing zeta functions of hyperelliptic curves over finite fields of characteristic 2

AU - Vercauteren, F

N1 - Editors: Moti Yung Publisher: Springer

PY - 2002/8

Y1 - 2002/8

N2 - We present an algorithm for computing the zeta function of an arbitrary hyperelliptic curve over a finite field $\FF_q$ of characteristic 2, thereby extending the algorithm of Kedlaya for small odd characteristic. For a genus $g$ hyperelliptic curve over $\FF_2^n$, the asymptotic running time of the algorithm is $O(g^5 + arepsilon n^3 + arepsilon)$ and the space complexity is $O(g^4 n^3)$.

AB - We present an algorithm for computing the zeta function of an arbitrary hyperelliptic curve over a finite field $\FF_q$ of characteristic 2, thereby extending the algorithm of Kedlaya for small odd characteristic. For a genus $g$ hyperelliptic curve over $\FF_2^n$, the asymptotic running time of the algorithm is $O(g^5 + arepsilon n^3 + arepsilon)$ and the space complexity is $O(g^4 n^3)$.

M3 - Conference Contribution (Conference Proceeding)

VL - 2442

SP - 369

EP - 384

BT - Advances in Cryptology -- CRYPTO 2002

PB - Springer Berlin Heidelberg

ER -

Computing zeta functions of hyperelliptic curves over finite fields of characteristic 2

Abstract

Bibliographical note

Access to Document

Handle.net

Fingerprint

Cite this