Computing isogenies between abelian varieties

DOI10.1112/S0010437X12000243MaRDI QIDQ3167320zbMATH OpenFDO

Authors David Lubicz, Damien Robert

Publication date 2 November 2012

Published in Compositio Mathematica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1001.2016

zbMATH Keywords

abelian varietyisogenypairingtheta functions

Mathematics Subject Classification ID

Isogeny (14K02) Theta functions and abelian varieties (14K25) Effectivity, complexity and computational aspects of algebraic geometry (14Q20)

Abstract: 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 $$ for $ellin{N}^{\ast }$, the overall time complexity of this algorithm is equivalent to $O(logell)$ additions in $A$ and a constant number of $el{l}^{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 $4ell$ of a $g$ dimensional abelian variety using only $g(g+1)/2cdot{4}^g$ coordinates. We also give formulas to compute the Weil and commutator pairings given input points in theta coordinates.

Recommendations

• Computing (\ell ,\ell )-isogenies in polynomial time on Jacobians of genus 2 curves
• Computing isogenies between Jacobians of curves of genus 2 and 3
• Computing functions on Jacobians and their quotients
• Fast change of level and applications to isogenies
• Computing separable isogenies in quasi-optimal time
• Cyclic isogenies for abelian varieties with real multiplication
• Gluing curves of genus 1 and 2 along their 2-torsion
• Rigid analytic uniformization of curves and the study of isogenies
• Computing the Selmer group of an isogeny between Abelian varieties using a further isogeny to a Jacobian
• Isogeny graphs of ordinary abelian varieties

Cites work

• Computing modular correspondences for abelian varieties
• Equations for the Jacobian of a hyperelliptic curve
• Fast genus 2 arithmetic based on Theta functions
• Higher-dimensional 3-adic CM construction
• Linear Systems on Abelian Varieties
• On the equations defining Abelian varieties. I-III
• The 2-Adic CM Method for Genus 2 Curves with Application to Cryptography
• The Weil pairing, and its efficient calculation

Cited in

(34)

• Computing the Abel map
• Translating the discrete logarithm problem on Jacobians of genus 3 hyperelliptic curves with \((\ell ,\ell ,\ell)\)-isogenies
• Constructing all genus 2 curves with supersingular Jacobian
• Isogeny graphs with maximal real multiplication
• Computational algorithm for reduction type of CM abelian varieties
• Rigid analytic uniformization of curves and the study of isogenies
• Subexponential time relations in the class group of large degree number fields
• Fast change of level and applications to isogenies
• Arithmetic on abelian and Kummer varieties
• Computing functions on Jacobians and their quotients
• Efficient pairing computation with theta functions
• Explicit arithmetic on abelian varieties
• Spanning the isogeny class of a power of an elliptic curve
• Cyclic isogenies for abelian varieties with real multiplication
• Computing separable isogenies in quasi-optimal time
• Computing isogenies between Jacobians of curves of genus 2 and 3
• Curves, Jacobians, and cryptography
• Computing (\ell ,\ell )-isogenies in polynomial time on Jacobians of genus 2 curves
• Computing endomorphism rings of abelian varieties of dimension two
• A new proof of a Thomae-like formula for non hyperelliptic genus 3 curves
• Computing the Cassels-Tate pairing on the Selmer group of a Richelot isogeny
• Theta nullvalues of supersingular abelian varieties
• Computing isogeny classes of typical principally polarized abelian surfaces over the rationals
• Efficient computation of \((2^n, 2^n)\)-isogenies
• Computing modular correspondences for abelian varieties
• SQIsignHD: new dimensions in cryptography
• Isogeny graphs of ordinary abelian varieties
• Fast computation of 2-isogenies in dimension 4 and cryptographic applications
• SQIsign2D-East: a new signature scheme using 2-dimensional isogenies
• Ideal-to-isogeny algorithm using 2-dimensional isogenies and its application to SQIsign
• Efficient theta-based algorithms for computing ( , )-isogenies on Kummer surfaces for arbitrary odd
• On the efficient representation of isogenies. A survey for NuTMiC 2024
• Superglue: fast formulae for (2,2)-gluing isogenies
• The supersingular endomorphism ring problem given one endomorphism

This page was built for publication: Computing isogenies between abelian varieties

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3167320)