Point counting in families of hyperelliptic curves

2006/01/18 by Hendrik Hubrechts, Hubrechts, H.
Computer Science · Mathematics · #11G20 (Primary) 12H25 #14F30 #14G50 (Secondary) #14Q05 #Algebraic Geometry (math.AG) #Algebraic Geometry and Number Theory #Cryptography and Residue Arithmetic #FOS: Mathematics #Number Theory (math.NT) #Polynomial and algebraic computation

paper · pdf · doi:10.48550/arxiv.math/0601438

openalex publication_date 2006/01/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let E_G be a family of hyperelliptic curves defined by Y²=Q(X,G), where Q is defined over a small finite field of odd characteristic. Then with g in an extension degree n field over this small field, we present a deterministic algorithm for computing the zeta function of the curve E_g by using Dwork deformation in rigid cohomology. The time complexity of the algorithm is O(n^(2.667)) and it needs O(n^(2.5)) bits of memory. A slight adaptation requires only O(n²) space, but costs time O(n³). An implementation of this last result turns out to be quite efficient for n big enough.

Citations

• Elliptic curve cryptosystems

Related

• Point counting in families of hyperelliptic curves in characteristic 2
• Memory efficient hyperelliptic curve point counting
• A point counting algorithm using cohomology with compact support
• Counting points on hyperelliptic curves in average polynomial time
• Quasi-quadratic elliptic curve point counting using rigid cohomology