Computing isogenies between abelian varieties

Details Computing isogenies between abelian varieties Computing isogenies between abelian varieties

2010-01-12

arxiv.org/abs/1001.2016v3

Mathematics

Algebraic Geometry

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Computing isogenies between abelian varieties does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Computing isogenies between abelian varieties, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computing isogenies between abelian varieties will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-523987