Article contents
Computing separable isogenies in quasi-optimal time
Published online by Cambridge University Press: 01 February 2015
Abstract
Let $A$ be an abelian variety of dimension $g$ together with a principal polarization ${\it\phi}:A\rightarrow \hat{A}$ defined over a field $k$. Let $\ell$ be an odd integer prime to the characteristic of $k$ and let $K$ be a subgroup of $A[\ell ]$ which is maximal isotropic for the Riemann form associated to ${\it\phi}$. We suppose that $K$ is defined over $k$ and let $B=A/K$ be the quotient abelian variety together with a polarization compatible with ${\it\phi}$. Then $B$, as a polarized abelian variety, and the isogeny $f:A\rightarrow 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 $\tilde{O} (\ell ^{(rg)/2})$ operations in $k$ where $r=2$ (respectively, $r=4$) if $\ell$ 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 $\ell$ is a sum of two squares since its complexity is quasi-linear in the degree of $f$.
MSC classification
- Type
- Research Article
- Information
- Copyright
- © The Author(s) 2015
References
- 5
- Cited by