Counting points on hyperelliptic curves in average polynomial time

2012/10/31 by Harvey, David · 2 citations
#11G25 #11Y99 #FOS: Mathematics #Number Theory (math.NT)

paper · doi:10.48550/arxiv.1210.8239

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² = 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.

Cited by

• Effective Artin-Schreier-Witt theory for curves
• Lifting L-polynomials of genus 2 curves

Related

• Memory efficient hyperelliptic curve point counting
• Point counting in families of hyperelliptic curves in characteristic 2
• Improved Complexity Bounds for Counting Points on Hyperelliptic Curves
• Lifting L-polynomials of genus 2 curves
• Point counting in families of hyperelliptic curves