Counting points on \(C_{ab}\) curves using Monsky-Washnitzer cohomology
type: Item
instance of: scholarly article
title: Counting points on \(C_{ab}\) curves using Monsky-Washnitzer cohomology
zbMATH Open document ID: 1104.11032
author: Frederik Vercauteren
author: Jan Denef
published in: Finite Fields and their Applications
publication date: 2006-02-07T00:00:00Z
review text: 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.
reviewed by: Christophe Ritzenthaler
Mathematics Subject Classification ID: 11G20
Mathematics Subject Classification ID: 94A60
Mathematics Subject Classification ID: 11T71
Mathematics Subject Classification ID: 11Y16
Mathematics Subject Classification ID: 14G15
Mathematics Subject Classification ID: 68W30
zbMATH DE Number: 5004387
zbMATH Keywords: \(C_{ab}\) curves
zbMATH Keywords: zeta function
zbMATH Keywords: Monsky-Washnitzer cohomology
zbMATH Keywords: cryptography
zbMATH Keywords: Kedlaya's algorithm
MaRDI profile type: Publication
full work available at URL: j.ffa.2005.01.003
OpenAlex ID: W2120966850
cites work: Q4375592
cites work: Counting points on curves and Abelian varieties over finite fields
cites work: A rigid analytic version of M. Artin's theorem on analytic equations
cites work: Q3139838
cites work: An extension of Kedlaya's algorithm to hyperelliptic curves in characteristic \(2\)
cites work: Solutions d'équations à coefficients dans un anneau hensélien
cites work: A Remark Concerning m-Divisibility and the Discrete Logarithm in the Divisor Class Group of Curves
cites work: Q5571530
cites work: Q4474195
cites work: Q4474194
cites work: Counting points on curves over finite fields
cites work: Q4542306
cites work: Elliptic Curve Cryptosystems
cites work: Hyperelliptic cryptosystems
cites work: Q3615934
cites work: Computing Zeta Functions of Artin–schreier Curves over Finite Fields
cites work: Computing zeta functions of Artin-Schreier curves over finite fields. II
cites work: Reducing elliptic curve logarithms to logarithms in a finite field
cites work: Q3718617
cites work: Formal cohomology. II: The cohomology sequence of a pair
cites work: Q5670721
cites work: Formal cohomology. III: Fixed point theorems
cites work: Formal cohomology. I
cites work: Frobenius Maps of Abelian Varieties and Finding Roots of Unity in Finite Fields
cites work: The canonical lift of an ordinary elliptic curve over a finite field and its point counting
cites work: Counting points on elliptic curves over finite fields
cites work: Q5601777
cites work: Q3744286
cites work: Q4409130
cites work: Numbers of solutions of equations in finite fields
DOI: 10.1016/J.FFA.2005.01.003
Recommended article: Computing zeta functions of nondegenerate curves
Recommended article: An extension of Kedlaya's algorithm to hyperelliptic curves in characteristic \(2\)
Recommended article: Kedlaya's Algorithm in Larger Characteristic
Recommended article: Computing zeta functions of arithmetic schemes
Recommended article: Computing Zeta Functions of Artin–schreier Curves over Finite Fields
Recommended article: MEMORY EFFICIENT HYPERELLIPTIC CURVE POINT COUNTING
Recommended article: Counting points on curves using a map to \(\mathbf P^1\). II.
Recommended article: Point counting in families of hyperelliptic curves
Recommended article: Counting points on curves using a map to \(\mathbf{P}^1\)
Recommended article: Q4542306
description: scientific article; zbMATH DE number 5004387