Theoretical Backgrounds of Applied Discrete Mathematics

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

N. S. Kolesnikov, S. A. Novoselov

Immanuel Kant Baltic Federal University, Kaliningrad, Russia

Abstract: 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, Frobenius action, $\ell$-torsion.

UDC: 512.742

Language: English

DOI: 10.17223/20710410/48/3

Bibliographic databases:

•