Computing modular correspondences for abelian varieties

In this paper, we describe an algorithm to compute modular correspondences in the coordinate system provided by the theta null points of abelian varieties together with a theta structure. As an application, this algorithm can be used to speed up the initialization phase of a point counting algorithm (Carls and Lubicz, 2008 [CL08]). The main part of the algorithm is the resolution of an algebraic system for which we have designed a specialized Gröbner basis algorithm. Our algorithm takes advantage of the structure of the algebraic system in order to speed up the resolution. We remark that this special structure comes from the action of the automorphisms of the theta group on the solutions of the system which has a nice geometric interpretation. In particular we were able to count the solutions of the system and to identify which ones correspond to valid theta null points.