Geodesic
On the distribution of orders of Frobenius action on $\ell$-torsion of abelian surfaces
Prikladnaâ diskretnaâ matematika, no. 2 (2020), pp. 22-33.

Voir la notice de l'article provenant de la source Math-Net.Ru

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 \pmod{\ell}$ to enumerate by using the formula $t^2 \equiv q (\zeta + \zeta^{-1})^2 \pmod{\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 \pmod{\ell}$ in order to replace these expensive computations by probabilistic algorithms.
Keywords: abelian varieties, finite fields
Mots-clés : Frobenius action, $\ell$-torsion. 
@article{PDM_2020_2_a2,
     author = {N. S. Kolesnikov and S. A. Novoselov},
     title = {On the distribution of orders of {Frobenius} action on $\ell$-torsion of abelian surfaces},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {22--33},
     publisher = {mathdoc},
     number = {2},
     year = {2020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/PDM_2020_2_a2/}
}
TY  - JOUR
AU  - N. S. Kolesnikov
AU  - S. A. Novoselov
TI  - On the distribution of orders of Frobenius action on $\ell$-torsion of abelian surfaces
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2020
SP  - 22
EP  - 33
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2020_2_a2/
LA  - en
ID  - PDM_2020_2_a2
ER  - 
%0 Journal Article
%A N. S. Kolesnikov
%A S. A. Novoselov
%T On the distribution of orders of Frobenius action on $\ell$-torsion of abelian surfaces
%J Prikladnaâ diskretnaâ matematika
%D 2020
%P 22-33
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2020_2_a2/
%G en
%F PDM_2020_2_a2
N. S. Kolesnikov; S. A. Novoselov. On the distribution of orders of Frobenius action on $\ell$-torsion of abelian surfaces. Prikladnaâ diskretnaâ matematika, no. 2 (2020), pp. 22-33. http://geodesic.mathdoc.fr/item/PDM_2020_2_a2/

[1] Schoof R., “Counting points on elliptic curves over finite fields”, J. de Théorie des Nombres de Bordeaux, 7:1 (1995), 219–254 | MR | Zbl

[2] Cohen H., Frey G., Avanzi R., et al., Handbook of Elliptic and Hyperelliptic Curve Cryptography, Chapman and Hall/CRC, 2005

[3] Silverman J. H., The Arithmetic of Elliptic Curves, Graduate Texts in Mathematics, 106, Springer Verlag, N.Y., 2009 | DOI | MR | Zbl

[4] Martindale C., Counting points on genus 2 curves over finite fields, Talk at GAGA Seminar in Utrecht, Netherlands, 2017

[5] Ballentine S., Guillevic A., García E. L., et al., “Isogenies for point counting on genus two hyperelliptic curves with maximal real multiplication”, Algebraic Geometry for Coding Theory and Cryptography, Springer, 2017, 63–94 | DOI | MR | Zbl

[6] Gaudry P., Schost É., “Genus 2 point counting over prime fields”, J. Symbolic Computation, 47:4 (2012), 368–400 | DOI | MR | Zbl

[7] Bröker R., Lauter K., “Modular polynomials for genus 2”, LMS J. Computation and Math., 12 (2009), 326–339 | DOI | MR

[8] Gaudry P., Schost É., “Modular equations for hyperelliptic curves”, Mathematics of Computation, 74:249 (2005), 429–454 | DOI | MR | Zbl

[9] Pila J., “Frobenius maps of abelian varieties and finding roots of unity in finite fields”, Mathematics of Computation, 55:192 (1990), 745–763 | DOI | MR | Zbl

[10] Kolesnikov N. S., Novoselov S. A., “On the order of the frobenius endomorphism action on $\ell$-torsion subgroup of abelian surfaces”, Prikl. Diskr. Mat. Suppl., 2019, no. 12, 11–12

[11] Tate J., “Endomorphisms of abelian varieties over finite fields”, Inventiones Mathematicae, 2:2 (1966), 134–144 | DOI | MR | Zbl

[12] Rück H.-G., “Abelian surfaces and jacobian varieties over finite fields”, Compositio Mathematica, 76:3 (1990), 351–366 | MR

[13] Bray J. N., Holt D. F., Roney-Dougal C. M., The Maximal Subgroups of the Low-Dimensional Finite Classical Groups, LMS Lecture Note Series, Cambridge University Press, 2013 | MR | Zbl

[14] Hurt N. E., Many Rational Points: Coding Theory and Algebraic Geometry, Mathematics and Its Applications, 564, Springer Science Business Media, 2013 | MR

[15] Stong R., “The average order of a matrix”, J. Combinatorial Theory, Ser. A, 64:2 (1993), 337–343 | DOI | MR | Zbl

[16] Schmutz E., “The order of a typical matrix with entries in a finite field”, Israel J. Mathematics, 91:1–3 (1995), 349–371 | DOI | MR | Zbl

[17] Fulman J., “Random matrix theory over finite fields”, Bull. Amer. Math. Society, 39:1 (2002), 51–85 | DOI | MR | Zbl

[18] Schmutz E., “The expected order of a random unitary matrix”, J. Group Theory, 11:4 (2008), 495–510 | DOI | MR | Zbl

[19] Aivazidis S., Sofos E., “On the distribution of the density of maximal order elements in general linear groups”, Ramanujan J., 38:1 (2015), 35–59 | DOI | MR | Zbl

[20] Srinivasan B., “The characters of the finite symplectic group $\operatorname{Sp}(4,q)$”, Trans. AMS, 131:2 (1968), 488–525 | MR | Zbl

[21] Diaconis P., Erdös P., “On the distribution of the greatest common divisor”, A Festschrift for Herman Rubin, Institute of Mathematical Statistics, 2004, 56–61 | DOI | MR | Zbl

[22] Achter J., Williams C., “Local heuristics and an exact formula for abelian surfaces over finite fields”, Canadian Math. Bull., 58:4 (2015), 673–691 | DOI | MR | Zbl

[23] SageMath, the Sage Mathematics Software System (Version 8.9), , 2019 https://www.sagemath.org

[24] Joux A., Lercier R., ““Chinese Match”, an alternative to Atkin's “Match and Sort” method used in the SEA algorithm”, Mathematics of Computation, 70:234 (2001), 827–836 | DOI | MR | Zbl