Counting points on hyperelliptic curves in average polynomial time
An hyperelliptic curve \(X\) of genus \(g\) and a rational Weierstrass point over a finite field \(\mathbb F_q\), \(q\) odd, can be written as \(y^2=Q(x)\) where \(Q\in\mathbb F_q\) is monic, square-free and of degree \(2g+1\). The zeta function of \(X\) has the form \[ Z_X(T)=\frac{P(T)}{(1-T)(1-qT)}, \] where \(P\in\mathbb Z[T]\) has degree \(2g\). An efficient algorithm for computing \(P(T)\), given \(q\), \(g\) and \(Q\), is useful for collecting data for the Birch-Swinnerton-Dyer conjecture and the Sato-Tate conjecture. Known algorithms for computing the zeta function have a time complexity that is exponential in either \(g\) or in \(\log p\). The author presents an algorithm that, for input \(N\geq 3\), \(g\geq 1\) and \(Q\in\mathbb Z[x]\) defining an hyperelliptic curve of genus \(g\), computes the sequence of zeta functions for \(\bar{X}_p\), over \(\mathbb F_p\), for all odd primes \(p < N\). The average time per prime is: \(g^{8+\epsilon}\log^3 N\log (\|Q\|N)\), which is polynomial in the size of the input (here \(\|Q\|\) denotes the maximum of the absolute values of the coefficients of \(Q\)). The starting point is \textit{K. S. Kedlaya}'s algorithm [J. Ramanujan Math. Soc. 16, No. 4, 323--338 (2001; Zbl 1066.14024)]. The portion of this algorithm whose complexity is exponential in \(\log p\) involves computing certain ``reduction matrices. The main improvement comes from replacing these by matrices that do not depend on \(p\). Then the author adopts the accumulating remainder tree algorithm of Costa, Gerbicz and Harvey, replacing its linear polynomials with his new matrices.
- Improved complexity bounds for counting points on hyperelliptic curves
- MEMORY EFFICIENT HYPERELLIPTIC CURVE POINT COUNTING
- Point counting in families of hyperelliptic curves
- Point counting in families of hyperelliptic curves in characteristic 2
- Computing Hasse-Witt matrices of hyperelliptic curves in average polynomial time
- A search for Wilson primes
- Algorithmic theory of zeta functions over finite fields
- An extension of Kedlaya's algorithm for hyperelliptic curves
- Computing L-Series of Hyperelliptic Curves
- Computing zeta functions of superelliptic curves in larger characteristic
- Constructing elliptic curves over finite fields with prescribed torsion
- Counting points on curves and Abelian varieties over finite fields
- Elliptic Curves Over Finite Fields and the Computation of Square Roots mod p
- Fast multiplication and its applications
- Formal cohomology. I
- Frobenius Maps of Abelian Varieties and Finding Roots of Unity in Finite Fields
- Gaussian elimination is not optimal
- Genus 2 point counting over prime fields
- scientific article; zbMATH DE number 1349933 (Why is no real title available?)
- scientific article; zbMATH DE number 610968 (Why is no real title available?)
- scientific article; zbMATH DE number 1936673 (Why is no real title available?)
- scientific article; zbMATH DE number 2081082 (Why is no real title available?)
- scientific article; zbMATH DE number 1775200 (Why is no real title available?)
- Hyperelliptic curves, L-polynomials, and random matrices
- Kedlaya's Algorithm in Larger Characteristic
- Linear Recurrences with Polynomial Coefficients and Application to Integer Factorization and Cartier–Manin Operator
- Sato-Tate distributions and Galois endomorphism modules in genus 2
- On the complexity of integer matrix multiplication
- Computation of étale cohomology on curves in single exponential time
- Counting points on hyperelliptic curves with explicit real multiplication in arbitrary genus
- On the paramodularity of typical abelian surfaces
- Zeta types and Tannakian symbols as a method for representing mathematical knowledge
- Counting points on curves using a map to \(\mathbf P^1\). II.
- Improved complexity bounds for counting points on hyperelliptic curves
- Fast computation of the \(N\)-th term of a \(q\)-holonomic sequence and applications
- Explicit bounds and heuristics on class numbers in hyperelliptic function fields
- Counting points on curves using a map to \(\mathbf{P}^1\)
- Computing Hasse-Witt matrices of hyperelliptic curves in average polynomial time
- Computing L-series of geometrically hyperelliptic curves of genus three
- Character theory approach to Sato-Tate groups
- An algorithm for computing the local zeta function of an hyperelliptic curve
- MEMORY EFFICIENT HYPERELLIPTIC CURVE POINT COUNTING
- Point counting in families of hyperelliptic curves in characteristic 2
- Computing Hasse-Witt matrices of hyperelliptic curves in average polynomial time. II
- Sato-Tate distributions
- A Hyperelliptic Smoothness Test, II
- Computing zeta functions of arithmetic schemes
- A p-Adic Quasi-Quadratic Time Point Counting Algorithm
- Computing \(L\)-polynomials of Picard curves from Cartier-Manin matrices
- On the distribution of Atkin and Elkies primes for reductions of elliptic curves on average
- Hypergeometric \(L\)-functions in average polynomial time
- Counting points on superelliptic curves in average polynomial time
- Frobenius structures on hypergeometric equations
- Computational Number Theory, Past, Present, and Future
- Counting points on genus-3 hyperelliptic curves with explicit real multiplication
- Computing zeta functions of cyclic covers in large characteristic
- Explicit Coleman integration in larger characteristic
- Zeta functions of nondegenerate hypersurfaces in toric varieties via controlled reduction in p-adic cohomology
- Fast Jacobian arithmetic for hyperelliptic curves of genus 3
- An extension of Kedlaya's algorithm for hyperelliptic curves
- Square root time Coleman integration on superelliptic curves
- Computing characteristic polynomials of p-curvatures in average polynomial time
- Computing the cohomology of constructible étale sheaves on curves
- Hypergeometric L-functions in average polynomial time. II
- Point counting in families of hyperelliptic curves
This page was built for publication: Counting points on hyperelliptic curves in average polynomial time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2445320)
