Counting points on curves over finite fields
The authors investigate the problem of giving an effective algorithm for the number \(N_{\mathcal C}\) of rational points of a curve \(\mathcal C\) over \(\mathbb F_q\) given by the zeros of a homogeneous polynomial \(F[x,y,z]\) defined over \(\mathbb F_q\). In 1948 André Weil proved the Riemann Hypothesis for curves over finite fields, namely, \(| N_{\mathcal C}-1-q| \leq 2gq^{1/2}\), where \(g\) denotes the genus of \(N_{\mathcal C}\). \textit{R. Schoof} [Math. Comput. 44, 483-494 (1985; Zbl 0579.14025)] gave a deterministic polynomial time algorithm for elliptic curves over finite fields. Later \textit{L. M. Adleman} and \textit{M.-D. Huang} [Primality testing and abelian varieties over finite fields, Lect. Notes Math. 1512, Springer-Verlag (1992; Zbl 0744.11065)] gave a random polynomial time algorithm for counting the number of \(\mathbb F_q\)-rational points of Jacobians curves of genus \(2\) over finite fields. This algorithm also applies to the estimate of \(N_{\mathcal C}\) itself. Moreover, \textit{J. Pila} [Math. Comput. 55, 745-763 (1990; Zbl 0724.11070)] showed that for a fixed curve \(\mathcal C\) defined over \(\mathbb Q\) by an absolutely irreducible polynomial \(F(x,y)\in \mathbb Q[x,y]\) there is a deterministic polynomial time algorithm which for each prime number \(p\) produces the number of rational points modulo \(p\) of \(\mathcal C\). The running time for the algorithm is \(O((\log p)^p)^{\Delta})\), where \(\Delta\) is at least doubly exponential on \(\deg(F)\). A little later, von zur Gathen showed that the number of \(\mathbb F_{q^n}\) rational points of a curve \(\mathcal C\) defined over \(\mathbb F_{q^n}\) of degree \(d\) can be calculated in \(\widetilde{O}(q^{d^2})\) operations over \(\mathbb F_{q^n}\), where \(n\geq 1\) denotes an integer and \(\widetilde{O}(t)\) means \(t(\log t+2)^{O(1)}\) operations over \(\mathbb F_q\) and an additional \(\widetilde{O}(n^2\log q)\) bit operations. The main result of this paper is an estimate for \(N_{\mathcal C}\) for a curve with just ordinary singularities. The bound obtained is that \(N_{\mathcal C}\) can be computed in randomized time \((\log q)^{\Delta}\), where \(\Delta=(\deg F)^{O(1)}\).
- scientific article; zbMATH DE number 66919
- Algorithmic Number Theory
- Counting points on curves and Abelian varieties over finite fields
- Frobenius Maps of Abelian Varieties and Finding Roots of Unity in Finite Fields
- Quasi-quadratic elliptic curve point counting using rigid cohomology
- scientific article; zbMATH DE number 1113820
- Fast computation of a rational point of a variety over a finite field
- An extension of Satoh's algorithm and its implementation
- scientific article; zbMATH DE number 1643934
- scientific article; zbMATH DE number 799785
- On the CM character of the curves \(y^ 2=x^ q-1\)
- Computing Riemann-Roch spaces in algebraic function fields and related topics.
- On counting and generating curves over small finite fields
- Counting points on hyperelliptic curves of type \(y^2=x^{2g+1}+ax^{g+1}+bx\)
- Counting points on smooth plane quartics
- Counting points on hyperelliptic curves with explicit real multiplication in arbitrary genus
- Rigid cohomology and \(p\)-adic point counting
- Counting points on curves using a map to \(\mathbf P^1\). II.
- Improved complexity bounds for counting points on hyperelliptic curves
- scientific article; zbMATH DE number 1588488 (Why is no real title available?)
- Computing discrete logarithms in high-genus hyperelliptic Jacobians in provably subexponential time
- Counting points on curves using a map to \(\mathbf{P}^1\)
- A heuristic for the distribution of point counts for random curves over a finite field
- Gaussian Point Count Statistics for Families of Curves Over a Fixed Finite Field
- Counting Points on Genus 2 Curves with Real Multiplication
- scientific article; zbMATH DE number 6019693 (Why is no real title available?)
- Fast computation of a rational point of a variety over a finite field
- A double large prime variation for small genus hyperelliptic index calculus
- The number of points on certain algebraic curves over finite fields
- Counting (quickly) the number of solutions of equations in finite fields
- scientific article; zbMATH DE number 5532114 (Why is no real title available?)
- scientific article; zbMATH DE number 1186969 (Why is no real title available?)
- Genus 2 point counting over prime fields
- scientific article; zbMATH DE number 1237890 (Why is no real title available?)
- Computing components and projections of curves over finite fields
- scientific article; zbMATH DE number 1306861 (Why is no real title available?)
- Sur le dénombrement des courbes de Fučik
- scientific article; zbMATH DE number 1113820 (Why is no real title available?)
- Finding Points on Curves over Finite Fields
- scientific article; zbMATH DE number 1555946 (Why is no real title available?)
- Point counting on curves using a gonality preserving lift
- Modular equations for hyperelliptic curves
- scientific article; zbMATH DE number 822740 (Why is no real title available?)
- Counting algorithms of points of a curve defined over a finite field
- Curves, dynamical systems, and weighted point counting
- Point counting on Picard curves in large characteristic
- Counting points on curves and Abelian varieties over finite fields
- Dichotomous point counts over finite fields
- Approximating Euler products and class number computation in algebraic function fields
- Counting points on genus-3 hyperelliptic curves with explicit real multiplication
- Counting curves and their projections
- Computing the cohomology of constructible étale sheaves on curves
- Counting points on \(C_{ab}\) curves using Monsky-Washnitzer cohomology
This page was built for publication: Counting points on curves over finite fields
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1382038)
