Computing separable isogenies in quasi-optimal time
arXiv:1402.3628 · doi:10.1112/S146115701400045X
Abstract
Let be an abelian variety of dimension together with a principal polarization defined over a field . Let be an odd integer prime to the characteristic of and let be a subgroup of which is maximal isotropic for the Riemann form associated to . We suppose that is defined over and let be the quotient abelian variety together with a polarization compatible with . Then , as a polarized abelian variety, and the isogeny are also defined over . In this paper, we describe an algorithm that takes as input a theta null point of and a polynomial system defining and outputs a theta null point of as well as formulas for the isogeny . We obtain a complexity of operations in where (resp. ) if is a sum of two squares (resp. if is a sum of four squares) which constitutes an improvement over the algorithm described in [7]. 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 .
References in corpus (7)
- Fast algorithms for computing isogenies between elliptic curves
- Computing the endomorphism ring of an ordinary elliptic curve over a finite field
- Computing Hilbert class polynomials with the Chinese Remainder Theorem
- Modular polynomials via isogeny volcanoes
- Computing isogenies between abelian varieties
- Computing modular correspondences for abelian varieties
- On polarised class groups of orders in quartic CM-fields