LOGIN TO YOUR ACCOUNT

Username
Password
Remember Me
Or use your Academic/Social account:

CREATE AN ACCOUNT

Or use your Academic/Social account:

Congratulations!

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.

Thank you for your patience,
OpenAire Dev Team.

Close This Message

CREATE AN ACCOUNT

Name:
Username:
Password:
Verify Password:
E-mail:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:
fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Lubicz, David; Robert, Damien (2010)
Publisher: Foundation Compositio Mathematica
Journal: Compositio Mathematica
Languages: English
Types: Article
Subjects: 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.
  • The results below are discovered through our pilot algorithms. Let us know how we are doing!

    • 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.
  • No related research data.
  • No similar publications.

Share - Bookmark

Funded by projects

  • EC | ANTICS

Cite this article