MEMORY EFFICIENT HYPERELLIPTIC CURVE POINT COUNTING

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

Authors: 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

Recommendations

• Kedlaya's Algorithm in Larger Characteristic
• Point counting in families of hyperelliptic curves
• Counting points on \(C_{ab}\) curves using Monsky-Washnitzer cohomology
• Counting points on hyperelliptic curves in average polynomial time
• Explicit Coleman integration in larger characteristic
• Computing zeta functions of arithmetic schemes
• An extension of Kedlaya's algorithm to hyperelliptic curves in characteristic \(2\)
• An extension of Kedlaya's algorithm for hyperelliptic curves
• Explicit \(p\)-adic method for elliptic and hyperelliptic curves
• scientific article; zbMATH DE number 1775200

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

• On fast multiplication of polynomials over arbitrary algebras
• Matrix multiplication via arithmetic progressions
• Title not available (Why is that?)
• 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 (16)

• Computing L-Series of Hyperelliptic Curves
• Fast computation of canonical lifts of elliptic curves and its application to point counting.
• Title not available (Why is that?)
• An extension of Kedlaya's algorithm for hyperelliptic curves
• A point counting algorithm using cohomology with compact support
• Improvements in the computation of the Hasse-Witt matrix
• 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
• Title not available (Why is that?)
• A low-memory algorithm for point counting on Picard curves
• A quasi quadratic time algorithm for hyperelliptic curve point counting
• Point counting in families of hyperelliptic curves in characteristic 2
• Point counting in families of hyperelliptic curves
• Title not available (Why is that?)

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)