HomeIssuesOn the distribution of orders of Frobenius action on ℓ-torsion of abelian surfaces

On the distribution of orders of Frobenius action on ℓ-torsion of abelian surfaces | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2020. № 48. DOI: 10.17223/20710410/48/3

The computation of the order of Frobenius action on the ℓ-torsion is a part of Schoof - Elkies - Atkin algorithm for point counting on an elliptic curve E over a finite field Fq. The idea of Schoof’s algorithm is to compute the trace of Frobenius t modulo primes ℓ and restore it by the Chinese remainder theorem. Atkin’s improvement consists of computing the order r of the Frobenius action on E[ℓ] and of restricting the number t (mod ℓ) to enumerate by using the formula t2 = q (ζ + ζ-1)2 (mod ℓ). Here ζ 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 ≡ 1 (mod ℓ) in order to replace these expensive computations by probabilistic algorithms.
Download file
Counter downloads: 108
  • Title On the distribution of orders of Frobenius action on ℓ-torsion of abelian surfaces
  • Headline On the distribution of orders of Frobenius action on ℓ-torsion of abelian surfaces
  • Publesher Tomask State UniversityTomsk State University
  • Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 48
  • Date:
  • DOI 10.17223/20710410/48/3
Keywords
абелевы поверхности, конечные поля, эндоморфизм Фробениуса, группа ℓ-кручения, abelian varieties, finite fields, Frobenius action, ℓ-torsion
Authors
References
Schoof R. Counting points on elliptic curves over finite fields. J. de Theorie des Nombres de Bordeaux, 1995, vol. 7, no. 1, pp. 219-254.
Cohen H., Frey G., Avanzi R., et al. Handbook of Elliptic and Hyperelliptic Curve Cryptography. Chapman and Hall/CRC, 2005.
Silverman J. H. The Arithmetic of Elliptic Curves. N.Y., Springer Verlag, 2009, vol. 106.
Martindale C. Counting points on genus 2 curves over finite fields. Talk at GAGA Seminar in Utrecht, Netherlands, 2017.
Ballentine S., Guillevic A., Garcia 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, pp. 63-94.
Gaudry P. and Schost E. Genus 2 point counting over prime fields. J. Symbolic Computation, 2012, vol. 47, no. 4, pp. 368-400.
Broker R. and Lauter K. Modular polynomials for genus 2. LMS J. Computation and Math., 2009, vol. 12, pp. 326-339.
Gaudry P. and Schost E. Modular equations for hyperelliptic curves. Mathematics of Computation, 2005, vol. 74, no. 249, pp. 429-454.
Pila J. Frobenius maps of abelian varieties and finding roots of unity in finite fields. Mathematics of Computation, 1990, vol. 55, no. 192, pp. 745-763.
Kolesnikov N. S. and Novoselov S. A. On the order of the frobenius endomorphism action on ℓ-torsion subgroup of abelian surfaces. Prikl. Diskr. Mat. Suppl., 2019, no. 12, pp. 11-12.
Tate J. Endomorphisms of abelian varieties over finite fields. Inventiones Mathematicae, 1966, vol. 2, no. 2, pp. 134-144.
Ruck H.-G. Abelian surfaces and jacobian varieties over finite fields. Compositio Mathematica, 1990, vol. 76, no. 3, pp. 351-366.
Bray J.N., Holt D.F., and Roney-Dougal C. M. The Maximal Subgroups of the Low Dimensional Finite Classical Groups. LMS Lecture Note Series, Cambridge University Press, 2013.
Hurt N. E. Many Rational Points: Coding Theory and Algebraic Geometry. Springer Science & Business Media, 2013, vol. 564.
Stong R. The average order of a matrix. J. Combinatorial Theory, Ser. A, 1993, vol. 64, no. 2, pp. 337-343.
Schmutz E. The order of a typical matrix with entries in a finite field. Israel J. Mathematics, 1995, vol. 91, no. 1-3, pp. 349-371.
Fulman J. Random matrix theory over finite fields. Bull. Amer. Math. Society, 2002, vol. 39, no. 1, pp.51-85.
Schmutz E. The expected order of a random unitary matrix. J. Group Theory, 2008, vol. 11, no. 4, pp.495-510.
Aivazidis S. and Sofos E. On the distribution of the density of maximal order elements in general linear groups. Ramanujan J., 2015, vol. 38, no. 1, pp. 35-59.
Srinivasan B. The characters of the finite symplectic group Sp(4, q). Trans. AMS, 1968, vol. 131, no. 2, pp. 488-525.
Diaconis P. and Erdos P. On the distribution of the greatest common divisor. A Festschrift for Herman Rubin, Institute of Mathematical Statistics, 2004, pp. 56-61.
Achter J. and Williams C. Local heuristics and an exact formula for abelian surfaces over finite fields. Canadian Math. Bull., 2015, vol. 58, no. 4, pp. 673-691.
SageMath, the Sage Mathematics Software System (Version 8.9), 2019. https://www. sagemath.org.
Joux A. and Lercier R. “Chinese & Match”, an alternative to Atkin’s “Match and Sort” method used in the SEA algorithm. Mathematics of Computation, 2001, vol. 70, no. 234, pp. 827-836.
On the distribution of orders of Frobenius action on ℓ-torsion of abelian surfaces | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2020. № 48. DOI: 10.17223/20710410/48/3
On the distribution of orders of Frobenius action on ℓ-torsion of abelian surfaces | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2020. № 48. DOI: 10.17223/20710410/48/3