Counting points on curves over finite fields
type: Item
instance of: scholarly article
title: Counting points on curves over finite fields
zbMATH Open document ID: 0919.11046
author: D. Massart
published in: Journal of Symbolic Computation
publication date: 1999-02-15T00:00:00Z
review text: 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 …
reviewed by: Amílcar Pacheco
Mathematics Subject Classification ID: 11G20
Mathematics Subject Classification ID: 11Y16
Mathematics Subject Classification ID: 14G15
Mathematics Subject Classification ID: 14Q05
zbMATH DE Number: 1136609
zbMATH Keywords: rational points
zbMATH Keywords: curves over finite fields
zbMATH Keywords: effective algorithm
MaRDI profile type: Publication
full work available at URL: jsco.1997.0164
OpenAlex ID: W2084377627
DOI: 10.1006/JSCO.1997.0164
Recommended article: Q4011586
Recommended article: Algorithmic Number Theory
Recommended article: Counting points on curves and Abelian varieties over finite fields
Recommended article: Frobenius Maps of Abelian Varieties and Finding Roots of Unity in Finite Fields
Recommended article: Quasi-quadratic elliptic curve point counting using rigid cohomology
Recommended article: Q4375592
Recommended article: Fast computation of a rational point of a variety over a finite field
Recommended article: An extension of Satoh's algorithm and its implementation
Recommended article: Q2739453
Recommended article: Q4847937
description: scientific article; zbMATH DE number 1136609