An extension of Kedlaya's algorithm to hyperelliptic curves in characteristic 2
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.
- Quasi-quadratic elliptic curve point counting using rigid cohomology
- Computing the 2-adic canonical lift of genus 2 curves
- Counting points on curves using a map to \(\mathbf P^1\). II.
- Higher-dimensional 3-adic CM construction
- Counting points on curves using a map to \(\mathbf{P}^1\)
- Computing Hasse-Witt matrices of hyperelliptic curves in average polynomial time
- MEMORY EFFICIENT HYPERELLIPTIC CURVE POINT COUNTING
- Point counting in families of hyperelliptic curves in characteristic 2
- Report on the Denef-Vercauteren/Kedlaya algorithm
- Computing Hasse-Witt matrices of hyperelliptic curves in average polynomial time. II
- scientific article; zbMATH DE number 1942432 (Why is no real title available?)
- scientific article; zbMATH DE number 2081082 (Why is no real title available?)
- scientific article; zbMATH DE number 1461531 (Why is no real title available?)
- scientific article; zbMATH DE number 1748068 (Why is no real title available?)
- 𝑝-adic point counting on singular superelliptic curves
- Counting Points in Medium Characteristic Using Kedlaya's Algorithm
- scientific article; zbMATH DE number 2086894 (Why is no real title available?)
- Approximating Euler products and class number computation in algebraic function fields
- Zeta functions of nondegenerate hypersurfaces in toric varieties via controlled reduction in p-adic cohomology
- Computing zeta functions of superelliptic curves in larger characteristic
- An extension of Kedlaya's algorithm for hyperelliptic curves
- Computing a group action from the class field theory of imaginary hyperelliptic function fields
- New characterizations of Dillon-like hyperbent functions via Dickson polynomials
- Counting points on \(C_{ab}\) curves using Monsky-Washnitzer cohomology
- Point counting in families of hyperelliptic curves
- Fast arithmetic in unramified \(p\)-adic fields
This page was built for publication: An extension of Kedlaya's algorithm to hyperelliptic curves in characteristic \(2\)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2499264)
