Counting points on curves over finite fields (Q1382038)

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)}\).