Counting points on C_ab curves using Monsky-Washnitzer cohomology
In this article, the authors describe an algorithm to compute the zeta function of any \(C_{ab}\)-curve over a finite field \(\mathbb{F}_{p^n}\). It is a generalization of Kedlaya's algorithm for hyperelliptic curves, and so find a \(p\)-adic approximation of the characteristic polynomial of Frobenius by computing in the Monsky-Washnitzer cohomology of the curve. The technique to lift the Frobenius endomorphism is different from [J. Cryptology 19, No. 1, 1--25 (2006; Zbl 1100.14017)] and can be applied to any non-singular affine curve. Furthermore the method used to prove a tight bound on the convergence rate of the resulting power series remains also valid. Only the explicit description of a basis of the first Monsky-Walshnitzer cohomology group and the reduction formulae to express a differential on this basis are limited to \(C_{ab}\) curves. For fixed \(p\) the asymptotic running time for \(C_{ab}\) curves of genus \(g\) over \(\mathbb{F}_{p^n}\) is \(O(g^{5+\varepsilon} n^{3+\varepsilon})\) and the space complexity is \(O(g^3 n^3)\). For instance the order of a \(168\)-bit Jacobian of a \(C_{3,4}\) curve can be computed in \(1.4\) h.
- Computing zeta functions of nondegenerate curves
- An extension of Kedlaya's algorithm to hyperelliptic curves in characteristic \(2\)
- Kedlaya's Algorithm in Larger Characteristic
- Computing zeta functions of arithmetic schemes
- Computing Zeta Functions of Artin–schreier Curves over Finite Fields
- MEMORY EFFICIENT HYPERELLIPTIC CURVE POINT COUNTING
- Counting points on curves using a map to \(\mathbf P^1\). II.
- Point counting in families of hyperelliptic curves
- Counting points on curves using a map to \(\mathbf{P}^1\)
- scientific article; zbMATH DE number 1775200
- A Remark Concerning m-Divisibility and the Discrete Logarithm in the Divisor Class Group of Curves
- A rigid analytic version of M. Artin's theorem on analytic equations
- An extension of Kedlaya's algorithm to hyperelliptic curves in characteristic \(2\)
- Computing zeta functions of Artin-Schreier curves over finite fields. II
- Computing Zeta Functions of Artin–schreier Curves over Finite Fields
- Counting points on curves and Abelian varieties over finite fields
- Counting points on curves over finite fields
- Counting points on elliptic curves over finite fields
- Elliptic Curve Cryptosystems
- Formal cohomology. I
- Formal cohomology. II: The cohomology sequence of a pair
- Formal cohomology. III: Fixed point theorems
- Frobenius Maps of Abelian Varieties and Finding Roots of Unity in Finite Fields
- scientific article; zbMATH DE number 435565 (Why is no real title available?)
- scientific article; zbMATH DE number 5532114 (Why is no real title available?)
- scientific article; zbMATH DE number 3948147 (Why is no real title available?)
- scientific article; zbMATH DE number 3979237 (Why is no real title available?)
- scientific article; zbMATH DE number 1113820 (Why is no real title available?)
- scientific article; zbMATH DE number 1942432 (Why is no real title available?)
- scientific article; zbMATH DE number 2081082 (Why is no real title available?)
- scientific article; zbMATH DE number 2081083 (Why is no real title available?)
- scientific article; zbMATH DE number 1775200 (Why is no real title available?)
- scientific article; zbMATH DE number 3288410 (Why is no real title available?)
- scientific article; zbMATH DE number 3322464 (Why is no real title available?)
- scientific article; zbMATH DE number 3404373 (Why is no real title available?)
- Hyperelliptic cryptosystems
- Numbers of solutions of equations in finite fields
- Reducing elliptic curve logarithms to logarithms in a finite field
- Solutions d'équations à coefficients dans un anneau hensélien
- The canonical lift of an ordinary elliptic curve over a finite field and its point counting
- Computing zeta functions of algebraic curves using Harvey's trace formula
- On infiniteness of integral overconvergent de Rham-Witt cohomology modulo torsion
- The uniqueness of Weierstrass points with semigroup \(\langle a;b\rangle \) and related semigroups
- Counting points on curves using a map to \(\mathbf P^1\). II.
- Curves in characteristic \(2\) with non-trivial \(2\)-torsion
- Counting points on curves using a map to \(\mathbf{P}^1\)
- Point counting on non-hyperelliptic genus 3 curves with automorphism group Z/2 Z using Monsky-Washnitzer cohomology
- MEMORY EFFICIENT HYPERELLIPTIC CURVE POINT COUNTING
- A point counting algorithm using cohomology with compact support
- Computing zeta functions of nondegenerate curves
- scientific article; zbMATH DE number 1775200 (Why is no real title available?)
- 𝑝-adic point counting on singular superelliptic curves
- Computing Zeta Functions in Families of C a,b Curves Using Deformation
- Algebraic independence in positive characteristic: a p-adic calculus
- Approximating Euler products and class number computation in algebraic function fields
- Computing zeta functions of cyclic covers in large characteristic
- Zeta functions of nondegenerate hypersurfaces in toric varieties via controlled reduction in p-adic cohomology
- Computing zeta functions of superelliptic curves in larger characteristic
- An extension of Kedlaya's algorithm for hyperelliptic curves
- A generalized Kiepert formula for \(C_{ab}\) curves
- On the exact evaluation of certain instances of the Potts partition function by quantum computers
- Fast arithmetic in unramified \(p\)-adic fields
This page was built for publication: Counting points on \(C_{ab}\) curves using Monsky-Washnitzer cohomology
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q814764)
