Counting points on curves and Abelian varieties over finite fields (Q5945287): Difference between revisions

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. This 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. For 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.