A p-Adic Quasi-Quadratic Time Point Counting Algorithm

DOI10.1093/IMRN/RNN143MaRDI QIDQ3613895zbMATH OpenOpenAlexFDO

Authors Robert Carls, David Lubicz

Publication date 16 March 2009

Published in IMRN. International Mathematics Research Notices (Search for Journal in Brave)

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

zbMATH Keywords

hyperellipticJacobianpoint countingtheta

Mathematics Subject Classification ID

Abelian varieties of dimension (> 1) (11G10) Curves over finite and local fields (11G20) Zeta functions and related questions in algebraic geometry (e.g., Birch-Swinnerton-Dyer conjecture) (14G10) Computational aspects of algebraic curves (14Q05)

Abstract: In this article we give an algorithm for the computation of the number of rational points on the Jacobian variety of a generic ordinary hyperelliptic curve defined over a finite field of cardinality $q$ with time complexity $O(n^{2+o(1)})$ and space complexity $O(n^2)$, where $n=log(q)$. In the latter complexity estimate the genus and the characteristic are assumed as fixed. Our algorithm forms a generalization of both, the AGM algorithm of J.-F. Mestre and the canonical lifting method of T. Satoh. We canonically lift a certain arithmetic invariant of the Jacobian of the hyperelliptic curve in terms of theta constants. The theta null values are computed with respect to a semi-canonical theta structure of level $2^{u}p$ where $u>0$ is an integer and $p=mathrmchar(F_q)>2$. The results of this paper suggest a global positive answer to the question whether there exists a quasi-quadratic time algorithm for the computation of the number of rational points on a generic ordinary abelian variety defined over a finite field.

Recommendations

• A quasi quadratic time algorithm for hyperelliptic curve point counting
• scientific article; zbMATH DE number 1113820
• Counting points on hyperelliptic curves in average polynomial time
• scientific article; zbMATH DE number 2009967
• Counting points on curves and Abelian varieties over finite fields

Cited in

(13)

• Quasi-quadratic elliptic curve point counting using rigid cohomology
• Computing the 2-adic canonical lift of genus 2 curves
• Higher-dimensional 3-adic CM construction
• A point counting algorithm for cyclic covers of the projective line
• Computing Igusa class polynomials
• An effective bound for the Huber constant for cofinite Fuchsian groups
• Simultaneous modular reduction and Kronecker substitution for small finite fields
• Algorithmic Number Theory
• The AGM-\(X_0(N)\) Heegner point lifting algorithm and elliptic curve point counting
• Counting points on genus-3 hyperelliptic curves with explicit real multiplication
• An extension of Kedlaya's algorithm for hyperelliptic curves
• Computing modular correspondences for abelian varieties
• A quasi quadratic time algorithm for hyperelliptic curve point counting

This page was built for publication: A p-Adic Quasi-Quadratic Time Point Counting Algorithm

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