On the distribution of orders of Frobenius action on $\ell$-torsion of abelian surfaces

Abstract

The computation of the order of Frobenius action on the $\ell$-torsion is a part of Schoof-Elkies-Atkin algorithm for point counting on an elliptic curve $E$ over a finite field ${\mathbb{F}}_q$. The idea of Schoof's algorithm is to compute the trace of Frobenius $t$ modulo primes $\ell$ and restore it by the Chinese remainder theorem. Atkin's improvement consists of computing the order $r$ of the Frobenius action on $E[\ell ]$ and of restricting the number $t(\mathrm{mod}\ell )$ to enumerate by using the formula $t^2\equiv q(\zeta +{\zeta }^{-1}{)}^2(\mathrm{mod}\ell )$. Here $\zeta$ is a primitive $r$-th root of unity. In this paper, we generalize Atkin's formula to the general case of abelian variety of dimension $g$. Classically, finding of the order $r$ involves expensive computation of modular polynomials. We study the distribution of the Frobenius orders in case of abelian surfaces and $q\equiv 1(\mathrm{mod}\ell )$ in order to replace these expensive computations by probabilistic algorithms.