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 )~δ) time where δ is polynomial in g as well as in N.