Computing separable isogenies in quasi-optimal time. Issue 1 (February 2015)

• Record Type: Journal Article
• Authors: Lubicz, David; Robert, Damien
• Is Part Of: LMS journal of computation and mathematics. Volume 18:Issue 1(2015)
• Page Start: 198
• Page End: 216
• Publication Date: 2015-02
• Subjects: 14K02, -- 14K25, -- 11G10
• DOI: 10.1112/S146115701400045X
• Languages: English
• ISSNs: 1461-1570

Abstract

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$ .