Geodesic
On the order of the Frobenius endomorphism action on $l$-torsion subgroup of Abelian surfaces
Prikladnaya Diskretnaya Matematika. Supplement, no. 12 (2019), pp. 11-12 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

One of the most powerful tools for point-counting on elliptic curves over finite fields is the Schoof–Elkies–Atkin algorithm. Its main idea is to construct characteristic polynomials for the action of the Frobenius endomorphim on $l$-torsion group. In this work, we study a probabilistic approach to find these characteristic polynomials in case of abelian surface. To do this, we introduce a random variable $\xi$ that takes values from a list ${r_1,\ldots,r_n}$, where $r_i$ is a possible order of Frobenius action on $l$-torsion subgroup. As soon as we have an explicit distribution of orders, we can obtain a characteristic polynomial in more effective way than in a classical Schoof-like algorithm. In this work, we derive formulas for calculating variance and standard deviation of the random variable $\xi$: $$ D(\xi)\approx \left(\frac{\pi^2}{48}\right)^2 \, \frac{\psi(l)}{l^2(l^2-1)^2}\, \frac{1}{\log^2(l)},\quad \sigma(\xi)=\sqrt{D(\xi)}\approx \frac{\pi^2}{48} \, \frac{\sqrt{\psi(l)}}{l(l^2-1)}\, \frac{1}{\log(l)}, $$ where $$ \psi(l)=2l^{10}+56l^9-316l^8+1344l^7-1948l^6-1770l^5+6660l^4-3516l^3-3831l^2+4684l-1369.$$
Keywords: Abelian surfaces, hyperelliptic curves, point-counting
Mots-clés : Frobenius endomorphism, $l$-torsion. 
@article{PDMA_2019_12_a1,
     author = {N. S. Kolesnikov and S. A. Novoselov},
     title = {On the order of the {Frobenius} endomorphism action on $l$-torsion subgroup of {Abelian} surfaces},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {11--12},
     year = {2019},
     number = {12},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2019_12_a1/}
}
TY  - JOUR
AU  - N. S. Kolesnikov
AU  - S. A. Novoselov
TI  - On the order of the Frobenius endomorphism action on $l$-torsion subgroup of Abelian surfaces
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2019
SP  - 11
EP  - 12
IS  - 12
UR  - http://geodesic.mathdoc.fr/item/PDMA_2019_12_a1/
LA  - ru
ID  - PDMA_2019_12_a1
ER  - 
%0 Journal Article
%A N. S. Kolesnikov
%A S. A. Novoselov
%T On the order of the Frobenius endomorphism action on $l$-torsion subgroup of Abelian surfaces
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2019
%P 11-12
%N 12
%U http://geodesic.mathdoc.fr/item/PDMA_2019_12_a1/
%G ru
%F PDMA_2019_12_a1
N. S. Kolesnikov; S. A. Novoselov. On the order of the Frobenius endomorphism action on $l$-torsion subgroup of Abelian surfaces. Prikladnaya Diskretnaya Matematika. Supplement, no. 12 (2019), pp. 11-12. http://geodesic.mathdoc.fr/item/PDMA_2019_12_a1/

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

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

[3] 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

[4] Novoselov S. A., Kolesnikov N. S., “On expected order of Frobenius action on $l$-torsion of abelian surfaces”, NuTMiC, 2019 (to appear) | Zbl

[5] Diaconis P., Erdös P., On the distribution of the greatest common divisor, Lecture Notes — Monograph Series, 45, Institute of Mathematical Statistics, 2004, 56–61 | DOI | MR | Zbl