Computing endomorphism rings of abelian varieties of dimension two

Bisson, Gaetan

doi:10.1090/S0025-5718-2015-02938-X

Computing endomorphism rings of abelian varieties of dimension two
HTML articles powered by AMS MathViewer

by Gaetan Bisson PDF

Math. Comp. 84 (2015), 1977-1989 Request permission

Abstract:

Generalizing a method of Sutherland and the author for elliptic cur ves we design a subexponential algorithm for computing the endomorphism rings of ordinary abelian varieties of dimension two over finite fields. Although its correctness and complexity analysis rest on several assumptions, we report on practical computations showing that it performs very well and can easily handle previously intractable cases.

Note. Some results of this paper previously appeared in the author’s thesis, [Endomorphism Rings in Cryptography, Ph.D. Thesis. Eindhoven University of Technology and Institut National Polytechnique de Lorraine, 2011. ISBN: 90-386-2519-7].

References

Gaetan Bisson, Computing endomorphism rings of elliptic curves under the GRH, J. Math. Cryptol. 5 (2011), no. 2, 101–113. MR 2838371, DOI 10.1515/JMC.2011.008
Gaetan Bisson, Endomorphism Rings in Cryptography, Ph.D. thesis. Eindhoven University of Technology and Institut National Polytechnique de Lorraine, 2011. ISBN: 90-386-2519-7.
Gaetan Bisson, Romain Cosset and Damien Robert, AVIsogenies, A library for computing isogenies between abelian varieties, 2010. http://avisogenies.gforge.inria.fr/.
Gaetan Bisson and Marco Steng, On polarised class groups of orders in quartic CM-fields, 2013. arXiv.org: 1302.3756.
Gaetan Bisson and Andrew V. Sutherland, Computing the endomorphism ring of an ordinary elliptic curve over a finite field, J. Number Theory 131 (2011), no. 5, 815–831. MR 2772473, DOI 10.1016/j.jnt.2009.11.003
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
Jean-Benoît Bost and Jean-François Mestre, Moyenne arithmético-géométrique et périodes des courbes de genre $1$ et $2$, Gaz. Math. 38 (1988), 36–64 (French). MR 970659
Reinier Bröker, David Gruenewald, and Kristin Lauter, Explicit CM theory for level 2-structures on abelian surfaces, Algebra Number Theory 5 (2011), no. 4, 495–528. MR 2870099, DOI 10.2140/ant.2011.5.495
Johannes Buchmann, A subexponential algorithm for the determination of class groups and regulators of algebraic number fields, Séminaire de Théorie des Nombres, Paris 1988–1989, Progr. Math., vol. 91, Birkhäuser Boston, Boston, MA, 1990, pp. 27–41. MR 1104698
Henri Cohen, Francisco Diaz y Diaz, and Michel Olivier, Subexponential algorithms for class group and unit computions, Journal of Symbolic Computation 24.3-4 (1997): Special Issue on Computational Algebra and Number Theory: Proceedings of the First MAGMA Conference, pp. 433–441. DOI:10.1006/jsco.1996.0143.
Gary Cornell and Joseph H. Silverman (eds.), Arithmetic geometry, Springer-Verlag, New York, 1986. Papers from the conference held at the University of Connecticut, Storrs, Connecticut, July 30–August 10, 1984. MR 861969, DOI 10.1007/978-1-4613-8655-1
Romain Cosset and Damien Robert, Computing $(l,l)$-isogenies in polynomial time on Jacobians of genus 2 curves, 2011. IACR ePrint: 2011/143.
J.-M. Couveignes, Linearizing torsion classes in the Picard group of algebraic curves over finite fields, J. Algebra 321 (2009), no. 8, 2085–2118. MR 2501511, DOI 10.1016/j.jalgebra.2008.09.032
Kirsten Eisenträger and Kristin Lauter, A CRT algorithm for constructing genus 2 curves over finite fields, Arithmetics, geometry, and coding theory (AGCT 2005), Sémin. Congr., vol. 21, Soc. Math. France, Paris, 2010, pp. 161–176 (English, with English and French summaries). MR 2856565
Mireille Fouquet and François Morain, Isogeny volcanoes and the SEA algorithm, Algorithmic Number Theory — ANTS-V, edited by Claus Ficker and David R. Kohel, vol. 2369, Lecture Notes in Computer Science, Springer, 2002, pp. 47–62. DOI: 10.1007/3-540-45455-1-23.
Steven D. Galbraith, Constructing isogenies between elliptic curves over finite fields, LMS J. Comput. Math. 2 (1999), 118–138. MR 1728955, DOI 10.1112/S1461157000000097
David Russell Kohel, Endomorphism rings of elliptic curves over finite fields, ProQuest LLC, Ann Arbor, MI, 1996. Thesis (Ph.D.)–University of California, Berkeley. MR 2695524
Arjen K. Lenstra and Hendrik W. Lenstra, editors, The Development of the Number Field Sieve, vol. 1554, Lecture Notes in Mathematics, Springer, 1993. ISBN: 3-540-57013-4.
H. W. Lenstra Jr. and Carl Pomerance, A rigorous time bound for factoring integers, J. Amer. Math. Soc. 5 (1992), no. 3, 483–516. MR 1137100, DOI 10.1090/S0894-0347-1992-1137100-0
David Lubicz and Damien Robert, Computing isogenies between abelian varieties, Compos. Math. 148 (2012), no. 5, 1483–1515. MR 2982438, DOI 10.1112/S0010437X12000243
Jean-François Mestre, Construction de courbes de genre $2$ à partir de leurs modules, Effective methods in algebraic geometry (Castiglioncello, 1990) Progr. Math., vol. 94, Birkhäuser Boston, Boston, MA, 1991, pp. 313–334 (French). MR 1106431
J. Pila, Frobenius maps of abelian varieties and finding roots of unity in finite fields, Math. Comp. 55 (1990), no. 192, 745–763. MR 1035941, DOI 10.1090/S0025-5718-1990-1035941-X
Goro Shimura and Yutaka Taniyama, Complex multiplication of abelian varieties and its applications to number theory, Publications of the Mathematical Society of Japan, vol. 6, Mathematical Society of Japan, Tokyo, 1961. MR 0125113
Andrew V. Sutherland, Computing Hilbert class polynomials with the Chinese remainder theorem, Math. Comp. 80 (2011), no. 273, 501–538. MR 2728992, DOI 10.1090/S0025-5718-2010-02373-7
John Tate, Endomorphisms of abelian varieties over finite fields, Invent. Math. 2 (1966), 134–144. MR 206004, DOI 10.1007/BF01404549
Jacques Vélu, Isogénies entre courbes elliptiques, C. R. Acad. Sci. Paris Sér. A-B 273 (1971), A238–A241 (French). MR 294345
Markus Wagner, Über Korrespondenzen zwischen algebraischen Funktionenkörper, Ph.D. thesis, Technische Universität Berlin, 2009. http://www.math.tu-berlin.de/~wagner/Diss.pdf.
William C. Waterhouse, Abelian varieties over finite fields, Ann. Sci. École Norm. Sup. (4) 2 (1969), 521–560. MR 265369