MEMORY EFFICIENT HYPERELLIPTIC CURVE POINT COUNTING
From MaRDI portal
Publication:3085111
Abstract: In recent algorithms that use deformation in order to compute the number of points on varieties over a finite field, certain differential equations of matrices over p-adic fields emerge. We present a novel strategy to solve this kind of equations in a memory efficient way. The main application is an algorithm requiring quasi-cubic time and only quadratic memory in the parameter n, that solves the following problem: for E a hyperelliptic curve of genus g over a finite field of extension degree n and small characteristic, compute its zeta function. This improves substantially upon Kedlaya's result which has the same quasi-cubic time asymptotic, but requires also cubic memory size.
Recommendations
- Kedlaya's Algorithm in Larger Characteristic
- Point counting in families of hyperelliptic curves
- Counting points on \(C_{ab}\) curves using Monsky-Washnitzer cohomology
- Counting points on hyperelliptic curves in average polynomial time
- Explicit Coleman integration in larger characteristic
- Computing zeta functions of arithmetic schemes
- An extension of Kedlaya's algorithm to hyperelliptic curves in characteristic \(2\)
- An extension of Kedlaya's algorithm for hyperelliptic curves
- Explicit \(p\)-adic method for elliptic and hyperelliptic curves
- scientific article; zbMATH DE number 1775200
Cites work
- scientific article; zbMATH DE number 1936673 (Why is no real title available?)
- An algorithm for polynomial multiplication that does not depend on the ring constants
- An extension of Kedlaya's algorithm to hyperelliptic curves in characteristic \(2\)
- Computing Zeta Functions in Families of C a,b Curves Using Deformation
- Deformation theory and the computation of zeta functions
- Fast arithmetic in unramified \(p\)-adic fields
- Matrix multiplication via arithmetic progressions
- On fast multiplication of polynomials over arbitrary algebras
- Point counting in families of hyperelliptic curves
- Point counting in families of hyperelliptic curves in characteristic 2
Cited in
(19)- An extension of Kedlaya's algorithm for hyperelliptic curves
- Improved complexity bounds for counting points on hyperelliptic curves
- Fast arithmetic in unramified \(p\)-adic fields
- A low-memory algorithm for point counting on Picard curves
- scientific article; zbMATH DE number 1808207 (Why is no real title available?)
- scientific article; zbMATH DE number 7119801 (Why is no real title available?)
- Counting points on curves using a map to \(\mathbf{P}^1\)
- A quasi quadratic time algorithm for hyperelliptic curve point counting
- A point counting algorithm using cohomology with compact support
- Computing zeta functions of generic projective hypersurfaces in larger characteristic
- Improvements in the computation of the Hasse-Witt matrix
- Computing Zeta Functions in Families of C a,b Curves Using Deformation
- scientific article; zbMATH DE number 2124950 (Why is no real title available?)
- Counting points on hyperelliptic curves in average polynomial time
- Fast computation of canonical lifts of elliptic curves and its application to point counting.
- Counting points on \(C_{ab}\) curves using Monsky-Washnitzer cohomology
- Point counting in families of hyperelliptic curves in characteristic 2
- Point counting in families of hyperelliptic curves
- Computing L-Series of Hyperelliptic Curves
This page was built for publication: MEMORY EFFICIENT HYPERELLIPTIC CURVE POINT COUNTING
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3085111)
