MEMORY EFFICIENT HYPERELLIPTIC CURVE POINT COUNTING

DOI10.1142/S1793042111004034zbMATH Open1222.11079arXivmath/0609032OpenAlexW2122931377MaRDI QIDQ3085111FDOQ3085111

Hendrik Hubrechts

Publication date: 28 March 2011

Published in: International Journal of Number Theory (Search for Journal in Brave)

Abstract: In recent algorithms that use deformation in order to compute the number of points on varieties over a finite field, certain differential equations of matrices over p-adic fields emerge. We present a novel strategy to solve this kind of equations in a memory efficient way. The main application is an algorithm requiring quasi-cubic time and only quadratic memory in the parameter n, that solves the following problem: for E a hyperelliptic curve of genus g over a finite field of extension degree n and small characteristic, compute its zeta function. This improves substantially upon Kedlaya's result which has the same quasi-cubic time asymptotic, but requires also cubic memory size.

Full work available at URL: https://arxiv.org/abs/math/0609032

zbMATH Keywords

differential equationdeformationhyperelliptic curvepoint counting

Mathematics Subject Classification ID

Curves over finite and local fields (11G20) (p)-adic cohomology, crystalline cohomology (14F30) Applications to coding theory and cryptography of arithmetic geometry (14G50) Computational aspects of algebraic curves (14Q05) Computational number theory (11Y99) (p)-adic differential equations (12H25)

Cites Work

• Title not available (Why is that?)
• On fast multiplication of polynomials over arbitrary algebras
• Matrix multiplication via arithmetic progressions
• Deformation theory and the computation of zeta functions
• An extension of Kedlaya's algorithm to hyperelliptic curves in characteristic \(2\)
• Computing Zeta Functions in Families of C a,b Curves Using Deformation
• Point counting in families of hyperelliptic curves
• Fast arithmetic in unramified \(p\)-adic fields
• Point Counting in Families of Hyperelliptic Curves in Characteristic 2
• An algorithm for polynomial multiplication that does not depend on the ring constants

Cited In (7)

• Title not available (Why is that?)
• An extension of Kedlaya's algorithm for hyperelliptic curves
• Computing zeta functions of generic projective hypersurfaces in larger characteristic
• Counting points on \(C_{ab}\) curves using Monsky-Washnitzer cohomology
• Computing Zeta Functions in Families of C a,b Curves Using Deformation
• Fast arithmetic in unramified \(p\)-adic fields
• Point counting in families of hyperelliptic curves

Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Kedlaya's Algorithm in Larger Characteristic 👍 👎
• An extension of Kedlaya's algorithm for hyperelliptic curves 👍 👎
• An extension of Kedlaya's algorithm to hyperelliptic curves in characteristic \(2\) 👍 👎
• Counting points on \(C_{ab}\) curves using Monsky-Washnitzer cohomology 👍 👎
• Counting points on hyperelliptic curves in average polynomial time 👍 👎
• Point counting in families of hyperelliptic curves 👍 👎
• Computing zeta functions of arithmetic schemes 👍 👎
• Explicit Coleman integration in larger characteristic 👍 👎

This page was built for publication: MEMORY EFFICIENT HYPERELLIPTIC CURVE POINT COUNTING

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3085111)