Counting points on hyperelliptic curves in average polynomial time
From MaRDI portal
Publication:2445320
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.
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
Cites work
- 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?)
- 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
- 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
Cited in
(36)- Explicit bounds and heuristics on class numbers in hyperelliptic function fields
- On the distribution of Atkin and Elkies primes for reductions of elliptic curves on average
- Sato-Tate distributions
- An extension of Kedlaya's algorithm for hyperelliptic curves
- Counting points on hyperelliptic curves with explicit real multiplication in arbitrary genus
- Computational Number Theory, Past, Present, and Future
- Improved complexity bounds for counting points on hyperelliptic curves
- Frobenius structures on hypergeometric equations
- 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
- Computing Hasse-Witt matrices of hyperelliptic curves in average polynomial time. II
- Computing \(L\)-series of geometrically hyperelliptic curves of genus three
- Square root time Coleman integration on superelliptic curves
- Hypergeometric \(L\)-functions in average polynomial time
- Counting points on curves using a map to \(\mathbf{P}^1\)
- Counting points on genus-3 hyperelliptic curves with explicit real multiplication
- 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
- A Hyperelliptic Smoothness Test, II
- Counting points on superelliptic curves in average polynomial time
- 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
- Character theory approach to Sato-Tate groups
- Point counting in families of hyperelliptic curves
- Computing characteristic polynomials of p-curvatures in average polynomial time
- Point counting in families of hyperelliptic curves in characteristic 2
- 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
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)
