You have just completed your registration at OpenAire.
Before you can login to the site, you will need to activate your account.
An e-mail will be sent to you with the proper instructions.
Important!
Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version
of the site upon release.
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.
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.