Point counting in families of hyperelliptic curves in characteristic 2

2006/07/14 by Hendrik Hubrechts, Hubrechts, Hendrik
Computer Science · Mathematics · #11G20 (Primary) 12H25 #14F30 #14G50 (Secondary) #14Q05 #Algebraic Geometry (math.AG) #Algebraic Geometry and Number Theory #Coding theory and cryptography #Cryptography and Residue Arithmetic #FOS: Mathematics #Number Theory (math.NT)

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

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

Abstract

Let E_G be a family of hyperelliptic curves over F2^(alg cl) with general Weierstrass equation given over a very small field F. We describe in this paper an algorithm to compute the zeta function of E_g for g in a degree n extension field of F, which has as time complexity O(n³) and memory requirements O(n²). With a slightly different algorithm we can get time O(n²,667) and memory O(n²,5), and the computation of O(n) curves of the family can be done in time and space O(n³). All these algorithms are polynomial in the genus.

Related

• Point counting in families of hyperelliptic curves
• Memory efficient hyperelliptic curve point counting
• Improved Complexity Bounds for Counting Points on Hyperelliptic Curves
• Enumerating hyperelliptic curves over finite fields in quasilinear time
• Counting points on hyperelliptic curves in average polynomial time