Counting points on curves and Abelian varieties over finite fields

We 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. For Abelian varieties of dimension g in projective N space over F-q, we improve Pila's result and show that the problem can be solved in O((log q)(delta)) time where delta is polynomial in g as well as in N. For hyperelliptic curves of genus g over F-q we show that the number of rational points on the curve and the number of rational points on its Jacobian can be computed in (log q)(O(g 2 log g)) time. (C) 2001 Academic Press.