This article is cited in 1 paper

Theoretical Foundations of Applied Discrete Mathematics

On the order of the Frobenius endomorphism action on $l$-torsion subgroup of Abelian surfaces

N. S. Kolesnikov, S. A. Novoselov

Immanuel Kant Baltic Federal University, Kaliningrad

Abstract: 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, Frobenius endomorphism, $l$-torsion.

UDC: 512.742

DOI: 10.17223/2226308X/12/2

Bibliographic databases:

•