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

The computation of the order of Frobenius action on the $\mathrm{\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 $\mathrm{\ell }$ and restore it by the Chinese remainder theorem. Atkin’s improvement consists of computing the order $r$ of the Frobenius action on $E[\mathrm{\ell }]$ and of restricting the number $t \pmod{\ell}$toenumeratebyusingtheformula$t^2 \equiv q (\zeta + \zeta^{-1})^2 \pmod{\ell}$\mathrm{.}Here$\zeta$isaprimitive$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{m}\mathrm{o}\mathrm{d}\mathrm{\ell })$ in order to replace these expensive computations by probabilistic algorithms.