Computing isogenies between abelian varieties

Article, Preprint English OPEN
Lubicz, David ; Robert, Damien (2010)
  • Publisher: Foundation Compositio Mathematica
  • Journal: Compositio Mathematica (issn: 0010-437X)
  • Related identifiers: doi: 10.1112/S0010437X12000243
  • Subject: 14K02 | Isogeny | [ INFO.INFO-SC ] Computer Science [cs]/Symbolic Computation [cs.SC] | Mathematics - Algebraic Geometry

We describe an efficient algorithm for the computation of separable isogenies between abelian varieties represented in the coordinate system given by algebraic theta functions. Let $A$ be an abelian variety of dimension $g$ defined over a field of odd characteristic. Our algorithm decomposes in two principal steps. First, given a theta null point for $A$ and a subgroup $K$ isotropic for the Weil pairing, we explain how to compute the theta null point corresponding to the quotient abelian variety $A/K$. Then, from the knowledge of a theta null point of $A/K$, we give an algorithm to obtain a rational expression for an isogeny from $A$ to $A/K$. The algorithm resulting as the combination of these two steps can be viewed as a higher dimensional analog of the well known algorithm of V\'elu to compute isogenies between elliptic curves. In the case that $K$ is isomorphic to $(\Z / \ell \Z)^g$ for $\ell \in \N^*$, the overall time complexity of this algorithm is equivalent to $O(\log \ell)$ additions in $A$ and a constant number of $\ell^{th}$ root extractions in the base field of $A$. In order to improve the efficiency of our algorithms, we introduce a compressed representation that allows to encode a point of level $4\ell$ of a $g$ dimensional abelian variety using only $g(g+1)/2\cdot 4^g$ coordinates. We also give formulas to compute the Weil and commutator pairings given input points in theta coordinates.
  • References (5)

    Corollary 4.16: Let xe, ye, x]y 2 Aek, and let i, j 2 Z(`n), k, l 2 Zˆ (`n). Then we have: We will use the affine lifts of points in Bk[`] that we have introduced in Section 4.1 to study this notion. Let M0 = [`] L0 on Bk and QBk,M0 a theta structure for M0 [Mum67b] D. Mumford. On the equations defining abelian varieties. III. Invent. Math., 3:215-244, 1967.

    [Mum83] David Mumford. Tata lectures on theta I, volume 28 of Progress in Mathematics.

    Birkhäuser Boston Inc., Boston, MA, 1983. With the assistance of C. Musili, M. Nori, E. Previato and M. Stillman.

    [Mum84] David Mumford. Tata lectures on theta II, volume 43 of Progress in Mathematics. Birkhäuser Boston Inc., Boston, MA, 1984. Jacobian theta functions and differential equations, With the collaboration of C. Musili, M. Nori, E.

    [Smi08] Benjamin Smith. Isogenies and the discrete logarithm problem in Jacobians of genus 3 hyperelliptic curves. Smart, Nigel (ed.), Advances in cryptology - EUROCRYPT 2008. 27th annual international conference on the theory and applications of cryptographic techniques, Istanbul, Turkey, April 13-17, 2008. Proceedings. Berlin: Springer. Lecture Notes in Computer Science 4965, 163-180 (2008)., 2008.

  • Metrics
    views in OpenAIRE
    views in local repository
    downloads in local repository
Share - Bookmark