An extension of Kedlaya's algorithm to hyperelliptic curves in characteristic \(2\) (Q2499264): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set OpenAlex properties. |
||
(3 intermediate revisions by 2 users not shown) | |||
Property / author | |||
Property / author: Jan Denef / rank | |||
Property / reviewed by | |||
Property / reviewed by: Enric Nart Viñals / rank | |||
Property / author | |||
Property / author: Jan Denef / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Enric Nart Viñals / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/s00145-004-0231-y / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2073392616 / rank | |||
Normal rank |
Latest revision as of 22:17, 19 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An extension of Kedlaya's algorithm to hyperelliptic curves in characteristic \(2\) |
scientific article |
Statements
An extension of Kedlaya's algorithm to hyperelliptic curves in characteristic \(2\) (English)
0 references
14 August 2006
0 references
The authors present an extension of Kedlaya's algorithm to compute the zeta function of an arbitrary hyperelliptic curve over a finite field of characteristic \(2\). The main difference with Kedlaya's algorithm is that the hyperelliptic curve can no longer be lifted arbitrarily to a \(2\)-adic ring; instead, a very specific lift is needed to ensure that the algebraic de Rham cohomology and the Monsky-Washnitzer cohomology are isomorphic. For a genus \(g\) hyperelliptic curve defined over the finite field with \(2^n\) elements, the average-case time complexity is \(O(g^{4+\varepsilon}n^{3+\varepsilon})\) and the average-case space complexity is \(O(g^3n^3)\), whereas the worst-case time and space complexities are \(O(g^{5+\varepsilon}n^{3+\varepsilon})\) and \(O(g^4n^3)\), respectively. An implementation in the C programming language shows that the cryptographic sizes are now feasible for any genus \(g\). For instance, computing the order of a \(160\)-bit Jacobian of a hyperelliptic curve of genus \(2,3,\) or \(4\) takes about \(75\) seconds. Several examples are given of hyperelliptic curves with these genera such that the group order of the Jacobian is divisible by a large prime number.
0 references