Hostname: page-component-cd9895bd7-jkksz Total loading time: 0 Render date: 2024-12-25T04:16:18.888Z Has data issue: false hasContentIssue false
  • English
  • Français

Computing isogenies between abelian varieties

Part of: Computational aspects in algebraic geometry Abelian varieties and schemes

Published online by Cambridge University Press:  10 July 2012

David Lubicz  and
Damien Robert
David Lubicz
Affiliation:
CÉLAR, BP 7419, 35174 Bruz Cedex, France (email: [email protected]) IRMAR, Universté de Rennes 1, Campus de Beaulieu, 35042 Rennes Cedex, France
Damien Robert
Affiliation:
INRIA Bordeaux – Sud-Ouest, 33405 Talence Cedex, France (email: [email protected])
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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 comprises 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 present an algorithm to obtain a rational expression for an isogeny from A to A/K. The algorithm that results from combining these two steps can be viewed as a higher-dimensional analog of the well-known algorithm of Vélu for computing isogenies between elliptic curves. In the case where K is isomorphic to (ℤ/ℓℤ)g for ℓ∈ℕ*, the overall time complexity of this algorithm is equivalent to O(log ℓ) additions in A and a constant number of ℓ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 us to encode a point of level 4ℓ of a g-dimensional abelian variety using only g(g+1)/2⋅4g coordinates. We also give formulas for computing the Weil and commutator pairings given input points in theta coordinates.

Keywords

isogenypairingtheta functions

MSC classification

Secondary: 14K02: Isogeny 14K25: Theta functions 14Q20: Effectivity, complexity
Type
Research Article
Information
Compositio Mathematica , Volume 148 , Issue 5 , September 2012 , pp. 1483 - 1515
Copyright
Copyright © Foundation Compositio Mathematica 2012

References

[ACDFLNV06]Avanzi, R., Cohen, H., Doche, C., Frey, G., Lange, T., Nguyen, K. and Vercauteren, F., Handbook of elliptic and hyperelliptic curve cryptography, Discrete Mathematics and its Applications, vol. 34, eds Cohen, H. and Frey, G. (Chapman & Hall/CRC, Boca Raton, FL, 2006).Google Scholar
[CKL08]Carls, R., Kohel, D. and Lubicz, D., Higher-dimensional 3-adic CM construction, J. Algebra 319 (2008), 971–1006.CrossRefGoogle Scholar
[FLR11]Faugère, J.-C., Lubicz, D. and Robert, D., Computing modular correspondences for abelian varieties, J. Algebra 343 (2011), 248–277.CrossRefGoogle Scholar
[FM02]Fouquet, M. and Morain, F., Isogeny volcanoes and the SEA algorithm, in Algorithmic number theory (Sydney, 2002), Lecture Notes in Computer Science, vol. 2369 (Springer, Berlin, 2002), 276–291.CrossRefGoogle Scholar
[Gau07]Gaudry, P., Fast genus 2 arithmetic based on theta functions, J. Math. Crypt. 1 (2007), 243–265.Google Scholar
[GHKRW06]Gaudry, P., Houtmann, T., Kohel, D., Ritzenthaler, C. and Weng, A., The 2-adic CM method for genus 2 curves with application to cryptography, in Advances in cryptology – ASIACRYPT 2006, Lecture Notes in Computer Science, vol. 4284 (Springer, Berlin, 2006), 114–129.CrossRefGoogle Scholar
[GS08]Gaudry, P. and Schost, E., Hyperelliptic curve point counting record: 254 bit Jacobian, June 2008, http://webloria.loria.fr/∼gaudry/record127/.Google Scholar
[Igu72]Igusa, J., Theta functions, Die Grundlehren der mathematischen Wissenschaften, Band 194 (Springer, New York, 1972).CrossRefGoogle Scholar
[Kem89]Kempf, G. R., Linear systems on abelian varieties, Amer. J. Math. 111 (1989), 65–94.CrossRefGoogle Scholar
[Koh96]Kohel, D., Endomorphism ring of elliptic curves over finite fields, PhD thesis, University of California, Berkeley (1996).Google Scholar
[Koh03]Kohel, D. R., The AGM-X0(N) Heegner point lifting algorithm and elliptic curve point counting, in Advances in cryptology – ASIACRYPT 2003, Lecture Notes in Computer Science, vol. 2894 (Springer, Berlin, 2003), 124–136.CrossRefGoogle Scholar
[Ler97]Lercier, R., Algorithmique des courbes elliptiques dans les corps finis, PhD thesis, L’École Polytechnique (1997).Google Scholar
[LR10]Lubicz, D. and Robert, D., Efficient pairing computation with theta functions, in Algorithmic number theory, Proc. 9th Int. Symp., Nancy, France, 19–23 July, 2010, Lecture Notes in Computer Science, vol. 6197, eds Hanrot, G., Morain, F. and Thomé, E. (Springer, 2010).Google Scholar
[Mil04]Miller, V. S., The Weil pairing, and its efficient calculation, J. Cryptology 17 (2004), 235–261.CrossRefGoogle Scholar
[Mum66]Mumford, D., On the equations defining abelian varieties. I, Invent. Math. 1 (1966), 287–354.CrossRefGoogle Scholar
[Mum70]Mumford, D., Abelian varieties, Tata Institute of Fundamental Research Studies in Mathematics, No. 5 (Tata Institute of Fundamental Research, Bombay, 1970).Google Scholar
[Ric36]Richelot, F., Essai sur une méthode générale pour déterminer la valeur des intégrales ultra-elliptiques, fondée sur des transformations remarquables de ces transcendantes, C. R. Acad. Sci. Paris 2 (1836), 622–627.Google Scholar
[Ric37]Richelot, F., De transformatione integralium abelianorum primiordinis commentation, J. Reine Angew. Math. 16 (1837), 221–341.Google Scholar
[Smi08]Smith, B., Isogenies and the discrete logarithm problem in Jacobians of genus 3 hyperelliptic curves, in Advances in cryptology – EUROCRYPT 2008 (27th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Istanbul, Turkey, April 13–17, 2008, Proceedings), Lecture Notes in Computer Science, vol. 4965, ed. Smart, N. (Springer, Berlin, 2008), 163–180.Google Scholar
[Vél71]Vélu, J., Isogénies entre courbes elliptiques, C. R. Acad. Sci. Paris Sér. A–B 273 (1971), A238–A241.Google Scholar
[Wam98]Wamelen, P., Equations for the Jacobian of a hyperelliptic curve, Trans. Amer. Math. Soc. 350 (1998), 3083–3106.CrossRefGoogle Scholar