Counting points on hyperelliptic curves in average polynomial time
From MaRDI portal
Publication:2445320
DOI10.4007/ANNALS.2014.179.2.7zbMATH Open1294.11104arXiv1210.8239OpenAlexW2157531996MaRDI QIDQ2445320FDOQ2445320
Authors: David I. Harvey 
Publication date: 14 April 2014
Published in: Annals of Mathematics. Second Series (Search for Journal in Brave)
Abstract: Let g >= 1 and let Q be a monic, squarefree polynomial of degree 2g + 1 in Z[x]. For an odd prime p not dividing the discriminant of Q, let Z_p(T) denote the zeta function of the hyperelliptic curve of genus g over the finite field F_p obtained by reducing the coefficients of the equation y^2 = Q(x) modulo p. We present an explicit deterministic algorithm that given as input Q and a positive integer N, computes Z_p(T) simultaneously for all such primes p < N, whose average complexity per prime is polynomial in g, log N, and the number of bits required to represent Q.
Full work available at URL: https://arxiv.org/abs/1210.8239
Recommendations
- 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
Curves over finite and local fields (11G20) Zeta and (L)-functions in characteristic (p) (11M38) Number-theoretic algorithms; complexity (11Y16)
Cites Work
- Title not available (Why is that?)
- Gaussian elimination is not optimal
- Elliptic Curves Over Finite Fields and the Computation of Square Roots mod p
- Genus 2 point counting over prime fields
- Title not available (Why is that?)
- Frobenius Maps of Abelian Varieties and Finding Roots of Unity in Finite Fields
- Sato-Tate distributions and Galois endomorphism modules in genus 2
- Title not available (Why is that?)
- Linear Recurrences with Polynomial Coefficients and Application to Integer Factorization and Cartier–Manin Operator
- Formal cohomology. I
- Title not available (Why is that?)
- Constructing elliptic curves over finite fields with prescribed torsion
- Kedlaya's Algorithm in Larger Characteristic
- Counting points on curves and Abelian varieties over finite fields
- An extension of Kedlaya's algorithm for hyperelliptic curves
- Title not available (Why is that?)
- Computing zeta functions of superelliptic curves in larger characteristic
- Computing L-Series of Hyperelliptic Curves
- Fast multiplication and its applications
- Algorithmic theory of zeta functions over finite fields
- Hyperelliptic curves, L-polynomials, and random matrices
- A search for Wilson primes
Cited In (36)
- On the distribution of Atkin and Elkies primes for reductions of elliptic curves on average
- Sato-Tate distributions
- Counting points on hyperelliptic curves with explicit real multiplication in arbitrary genus
- An extension of Kedlaya's algorithm for hyperelliptic curves
- Computational Number Theory, Past, Present, and Future
- Frobenius structures on hypergeometric equations
- Improved complexity bounds for counting points on hyperelliptic curves
- On the complexity of integer matrix multiplication
- Counting points on curves using a map to \(\mathbf P^1\). II.
- MEMORY EFFICIENT HYPERELLIPTIC CURVE POINT COUNTING
- Square root time Coleman integration on superelliptic curves
- Computing Hasse-Witt matrices of hyperelliptic curves in average polynomial time. II
- Hypergeometric \(L\)-functions in average polynomial time
- Computing \(L\)-series of geometrically hyperelliptic curves of genus three
- Counting points on genus-3 hyperelliptic curves with explicit real multiplication
- Counting points on curves using a map to \(\mathbf{P}^1\)
- Zeta types and Tannakian symbols as a method for representing mathematical knowledge
- Fast computation of the \(N\)-th term of a \(q\)-holonomic sequence and applications
- Computing zeta functions of arithmetic schemes
- An algorithm for computing the local zeta function of an hyperelliptic curve
- Computing zeta functions of cyclic covers in large characteristic
- Fast Jacobian arithmetic for hyperelliptic curves of genus 3
- Computing Hasse-Witt matrices of hyperelliptic curves in average polynomial time
- Counting points on superelliptic curves in average polynomial time
- A Hyperelliptic Smoothness Test, II
- Explicit Coleman integration in larger characteristic
- A p-Adic Quasi-Quadratic Time Point Counting Algorithm
- On the paramodularity of typical abelian surfaces
- Computation of étale cohomology on curves in single exponential time
- Computing characteristic polynomials of p-curvatures in average polynomial time
- Character theory approach to Sato-Tate groups
- Point counting in families of hyperelliptic curves in characteristic 2
- Point counting in families of hyperelliptic curves
- Zeta functions of nondegenerate hypersurfaces in toric varieties via controlled reduction in \(p\)-adic cohomology
- Computing \(L\)-polynomials of Picard curves from Cartier-Manin matrices
- Explicit bounds and heuristics on class numbers in hyperelliptic function fields
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)
