## Counting points on curves over finite fields.(English)Zbl 0919.11046

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}$$.
R. Schoof [Math. Comput. 44, 483-494 (1985; Zbl 0579.14025)] gave a deterministic polynomial time algorithm for elliptic curves over finite fields. Later L. M. Adleman and 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, 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)}$$.

### MSC:

 11G20 Curves over finite and local fields 11Y16 Number-theoretic algorithms; complexity 14G15 Finite ground fields in algebraic geometry 14Q05 Computational aspects of algebraic curves

### Citations:

Zbl 0579.14025; Zbl 0744.11065; Zbl 0724.11070
Full Text: