Counting points on curves and Abelian varieties over finite fields (Q5945287)

The authors develop efficient methods for deterministic computations with semi-algebraic sets and apply them to the problem of counting points on curves and Abelian varieties over finite fields.NEWLINENEWLINENEWLINEThis type of problem has drawn considerable interest in recent years. \textit{R. Schoof} [Math. Comput. 44, 483-494 (1985; Zbl 0579.14025)] gave a deterministic polynomial time algorithm for the case of elliptic curves and applied it to solve, for a fixed integer \(a\), \(x^2\equiv a\pmod p\) in deterministic polynomial time on input primes \(p\). \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)] proved a primality testing algorithm which involved a random polynomial time algorithm for counting rational points on Jacobians of curves of genus \(2\) over finite fields. \textit{J. Pila} [Math. Comput. 55, 745-763 (1990; Zbl 0724.11070)] showed that for a fixed curve over the rationals, the number of rational points on the reduction of the curve and its Jacobian modulo a prime can be computed in deterministic polynomial time. The result is applied to solve, for fixed \(l\), \(\Phi_l(x)\equiv 0\pmod p\) in deterministic polynomial time on input primes \(p\), where \(\Phi_l\) denotes the \(l\)-th cyclotomic polynomial.NEWLINENEWLINENEWLINEFor Abelian varieties, the authors improve on the result of Pila showing that an Abelian variety of dimension \(g\) in \({\mathbb{P}}^N_{{\mathbb{F}}_q}\), the problem can be solved in \(O(\log q)^{\delta}\) time, where \(\delta\) is a polynomial in \(g\) and in \(N\). For Jacobians of hyperelliptic curves, they show an even better result. The number of rational points can be obtained in \((\log q)^{O(g^2\log g)}\) time.