Computing isogenies between Jacobians of curves of genus 2 and 3

Milio, Enea

doi:10.1090/mcom/3486

Computing isogenies between Jacobians of curves of genus 2 and 3
HTML articles powered by AMS MathViewer

by Enea Milio;

Math. Comp. 89 (2020), 1331-1364

DOI: https://doi.org/10.1090/mcom/3486

Published electronically: October 28, 2019

HTML | PDF | Request permission

Abstract:

We present a quasi-linear algorithm to compute (separable) isogenies of degree $\ell ^g$, for $\ell$ an odd prime number, between Jacobians of curves of genus $g=2$ and $3$ starting from the equation of the curve $\mathcal {C}$ and a maximal isotropic subgroup $\mathcal {V}$ of the $\ell$-torsion, generalizing Vélu’s formula from genus $1$. Denoting by $J_{\mathcal {C}}$ the Jacobian of $\mathcal {C}$, the isogeny is $J_{\mathcal {C}}\to J_{\mathcal {C}}/\mathcal {V}$. Thus $\mathcal {V}$ is the kernel of the isogeny and we compute only isogenies with such kernels. This work is based on the paper Computing functions on Jacobians and their quotients of Jean-Marc Couveignes and Tony Ezome. We improve their genus $2$ algorithm, generalize it to genus $3$ hyperelliptic curves, and introduce a way to deal with the genus $3$ nonhyperelliptic case, using algebraic theta functions.

References

Christina Birkenhake and Herbert Lange, Complex abelian varieties, 2nd ed., Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 302, Springer-Verlag, Berlin, 2004. MR 2062673, DOI 10.1007/978-3-662-06307-1
G. Bisson, R. Cosset, and D. Robert. AVIsogenies (Abelian Varieties and Isogenies). Magma package for explicit isogenies computation between abelian varieties. http://avisogenies.gforge.inria.fr/, 2010.
Wieb Bosma, John Cannon, and Catherine Playoust, The Magma algebra system. I. The user language, J. Symbolic Comput. 24 (1997), no. 3-4, 235–265. Computational algebra and number theory (London, 1993). MR 1484478, DOI 10.1006/jsco.1996.0125
A. Bostan, F. Morain, B. Salvy, and É. Schost, Fast algorithms for computing isogenies between elliptic curves, Math. Comp. 77 (2008), no. 263, 1755–1778. MR 2398793, DOI 10.1090/S0025-5718-08-02066-8
L. Brambila-Paz, S.B. Bradlow, O. Garca-Prada, and S. Ramanan. Moduli Spaces and Vector Bundles, volume 359 of London Mathematical Society Lecture Note Series. Cambridge University Press, 2009.
Lucia Caporaso and Edoardo Sernesi, Recovering plane curves from their bitangents, J. Algebraic Geom. 12 (2003), no. 2, 225–244. MR 1949642, DOI 10.1090/S1056-3911-02-00307-7
J. W. S. Cassels and E. V. Flynn, Prolegomena to a middlebrow arithmetic of curves of genus $2$, London Mathematical Society Lecture Note Series, vol. 230, Cambridge University Press, Cambridge, 1996. MR 1406090, DOI 10.1017/CBO9780511526084
R. Cosset, Applications des fonctions thêta à la cryptographie sur courbes hyperelliptiques, PhD thesis, Université Henri Poincaré - Nancy 1, 2011.
Romain Cosset and Damien Robert, Computing $(\ell ,\ell )$-isogenies in polynomial time on Jacobians of genus $2$ curves, Math. Comp. 84 (2015), no. 294, 1953–1975. MR 3335899, DOI 10.1090/S0025-5718-2014-02899-8
Jean-Marc Couveignes and Tony Ezome, Computing functions on Jacobians and their quotients, LMS J. Comput. Math. 18 (2015), no. 1, 555–577. MR 3389883, DOI 10.1112/S1461157015000169
C. Diem, On arithmetic and the discrete logarithm problem in class groups of curves, 2008.
I. Dolgachev and D. Lehavi, On isogenous principally polarized abelian surfaces, Curves and abelian varieties, Contemp. Math., vol. 465, Amer. Math. Soc., Providence, RI, 2008, pp. 51–69. MR 2457735, DOI 10.1090/conm/465/09100
A. Fiorentino, Weber’s formula for the bitangents of a smooth plane quartic, arXiv:1612.02049, 2016.
Phillip Griffiths and Joseph Harris, Principles of algebraic geometry, Pure and Applied Mathematics, Wiley-Interscience [John Wiley & Sons], New York, 1978. MR 507725
Jun-ichi Igusa, Theta functions, Die Grundlehren der mathematischen Wissenschaften, Band 194, Springer-Verlag, New York-Heidelberg, 1972. MR 325625
George R. Kempf, Linear systems on abelian varieties, Amer. J. Math. 111 (1989), no. 1, 65–94. MR 980300, DOI 10.2307/2374480
Shoji Koizumi, Theta relations and projective normality of Abelian varieties, Amer. J. Math. 98 (1976), no. 4, 865–889. MR 480543, DOI 10.2307/2374034
Serge Lang, Abelian varieties, Interscience Tracts in Pure and Applied Mathematics, No. 7, Interscience Publishers, Inc., New York; Interscience Publishers Ltd., London, 1959. MR 106225
David Lehavi, Any smooth plane quartic can be reconstructed from its bitangents, Israel J. Math. 146 (2005), 371–379. MR 2151609, DOI 10.1007/BF02773542
D. Lehavi and C. Ritzenthaler, An explicit formula for the arithmetic-geometric mean in genus 3, Experiment. Math. 16 (2007), no. 4, 421–440. MR 2378484
David Lubicz and Damien Robert, Computing isogenies between abelian varieties, Compos. Math. 148 (2012), no. 5, 1483–1515. MR 2982438, DOI 10.1112/S0010437X12000243
David Lubicz and Damien Robert, Computing separable isogenies in quasi-optimal time, LMS J. Comput. Math. 18 (2015), no. 1, 198–216. MR 3349315, DOI 10.1112/S146115701400045X
D. Mumford, On the equations defining abelian varieties. I, Invent. Math. 1 (1966), 287–354. MR 204427, DOI 10.1007/BF01389737
D. Mumford, On the equations defining abelian varieties. II, Invent. Math. 3 (1967), 75–135. MR 219541, DOI 10.1007/BF01389741
D. Mumford, On the equations defining abelian varieties. III, Invent. Math. 3 (1967), 215–244. MR 219542, DOI 10.1007/BF01425401
D. Mumford. Tata lectures on theta I, volume 28 of Progress in Mathematics. Birkhäuser Boston, 1983.
D. Mumford. Tata lectures on theta II, volume 43 of Progress in Mathematics. Birkhäuser Boston, 1984.
J. Steffen Müller, Explicit Kummer varieties of hyperelliptic Jacobian threefolds, LMS J. Comput. Math. 17 (2014), no. 1, 496–508. MR 3356043, DOI 10.1112/S1461157014000126
Sevin Recillas, Jacobians of curves with $g^{1}_{4}$’s are the Prym’s of trigonal curves, Bol. Soc. Mat. Mexicana (2) 19 (1974), no. 1, 9–13. MR 480505
B. Riemann, Sur la Théorie des Fonctions Abéliennes, Oeuvres de Riemann, second edition, p. 487, 1898.
Christophe Ritzenthaler, Point counting on genus 3 non hyperelliptic curves, Algorithmic number theory, Lecture Notes in Comput. Sci., vol. 3076, Springer, Berlin, 2004, pp. 379–394. MR 2138009, DOI 10.1007/978-3-540-24847-7_{2}9
C. Ritzenthaler, Problèmes arithmétiques relatifs à certaines familles de courbes sur les corps finis, PhD thesis, Université Paris 7 – Denis Diderot, June 2003.
D. Robert, Fonctions thêta et applications à la cryptographie, PhD thesis, Université Henri Poincaré – Nancy 1, 2010.
Benjamin Smith, Isogenies and the discrete logarithm problem in Jacobians and genus 3 hyperelliptic curves, Advances in cryptology—EUROCRYPT 2008, Lecture Notes in Comput. Sci., vol. 4965, Springer, Berlin, 2008, pp. 163–180. MR 2606332, DOI 10.1007/978-3-540-78967-3_{1}0
Benjamin Smith, Computing low-degree isogenies in genus 2 with the Dolgachev-Lehavi method, Arithmetic, geometry, cryptography and coding theory, Contemp. Math., vol. 574, Amer. Math. Soc., Providence, RI, 2012, pp. 159–170. MR 2961408, DOI 10.1090/conm/574/11418
Michael Stoll, An explicit theory of heights for hyperelliptic Jacobians of genus three, Algorithmic and experimental methods in algebra, geometry, and number theory, Springer, Cham, 2017, pp. 665–715. MR 3792747
A. G. J. Stubbs, Hyperelliptic curves, PhD thesis, University of Liverpool, 2000.
J. Vélu, Isogénies Entre Courbes Elliptiques, Compte Rendu Académie Sciences Paris Série A-B, 273:A238–A241, 1971.
H. Weber, Theorie der Abelschen Funktionen vom Geschlecht 3, Berlin : Druck und Verlag von Georg Reimer, 1876.
A. Weng, Konstruktion kryptographisch geeigneter Kurven mit komplexer Multiplikation, PhD thesis, Universität GH Essen, 2001.