Counting rational points on curves and abelian varieties over finite fields (Q4375592)

Let \(A\) be an abelian variety of dimension \(g\) over a finite field \({\mathbb F}_q\). Suppose that \(A\) is given as a closed subvariety of projective \(n\)-space. The authors exhibit a deterministic algorithm that computes the characteristic polynomial of the Frobenius endomorphism of \(A\) that runs in time \(O((\log q)^c)\), where \(c\) is a polynomial expression in \(g\) as well as \(n\). This improves upon an earlier result of \textit{J. Pila} [Math. Comput. 55, 745--763 (1990; Zbl 0724.11070)], who obtained a similar result but with the constant \(c\) depending exponentially on \(n\). By applying this to the Jacobian varieties of curves \(X\) over \({\mathbb F}_q\), one obtains a deterministic algorithm to count the number of \(\mathbb F_q\)-rational points of \(X\) that runs in time \(O((\log q)^c)\), where \(c\) is a polynomial expression in \(n\), as well as the genus \(g\) of \(X\). In the special case of hyperelliptic curves of genus \(g\), the authors show that the number of \(\mathbb F_q\)-rational points on \(X\) can be counted deterministically in time \((\log q)^{O(g^6)}\). This case is of interest in view of the primality test described by the authors in their monograph [Primality testing and abelian varieties over finite fields, Lect. Notes Math. 1512. Berlin etc.: Springer-Verlag (1992; Zbl 0744.11065)]. For the entire collection see [Zbl 0852.00023].