Computing separable isogenies in quasi-optimal time. Issue 1 (February 2015) - Lubicz, David; Robert, Damien
Abstract: Let A be an abelian variety of dimension g together with a principal polarization φ:A→ A defined over a field k . Let be an odd integer prime to the characteristic of k and let K be a subgroup of A[] which is maximal isotropic for the Riemann form associated to φ . We suppose that K is defined over k and let B=A/K be the quotient abelian variety together with a polarization compatible with φ . Then B, as a polarized abelian variety, and the isogeny f:A→ B are also defined over k . In this paper, we describe an algorithm that takes as input a theta null point of A and a polynomial system defining K and outputs a theta null point of B as well as formulas for the isogeny f . We obtain a complexity of O (^(rg)/2) operations in k where r=2 (respectively, r=4 ) if is a sum of two (respectively, four) squares which constitutes an improvement over the algorithm described in Cosset and Robert ( Math. Comput. (2013) accepted for publication). We note that the algorithm is quasi-optimal if is a sum of two squares since its complexity is quasi-linear in the degree of f .