Top

Published in:

2017 | OriginalPaper | Chapter

3. Isogenies for Point Counting on Genus Two Hyperelliptic Curves with Maximal Real Multiplication

Authors : Sean Ballentine, Aurore Guillevic, Elisa Lorenzo García, Chloe Martindale, Maike Massierer, Benjamin Smith, Jaap Top

Published in: Algebraic Geometry for Coding Theory and Cryptography

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Schoof’s classic algorithm allows point-counting for elliptic curves over finite fields in polynomial time. This algorithm was subsequently improved by Atkin, using factorizations of modular polynomials, and by Elkies, using a theory of explicit isogenies. Moving to Jacobians of genus-2 curves, the current state of the art for point counting is a generalization of Schoof’s algorithm. While we are currently missing the tools we need to generalize Elkies’ methods to genus 2, recently Martindale and Milio have computed analogues of modular polynomials for genus-2 curves whose Jacobians have real multiplication by maximal orders of small discriminant. In this chapter, we prove Atkin-style results for genus-2 Jacobians with real multiplication by maximal orders, with a view to using these new modular polynomials to improve the practicality of point-counting algorithms for these curves.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Hypersurfaces in Weighted Projective Spaces Over Finite Fields with Applications to Coding Theory

next chapter Locally Recoverable Codes from Algebraic Curves and Surfaces

We would also like to mention Bisson, Cosset, and Robert’s AVIsogenies software package [1], which provides some functionality in this direction. However, their methods apply to abelian surfaces with a lot of rational 2- and 4-torsion, and applying them to general genus-2 Jacobians (with or without known RM) generally requires a substantial extension of the base field to make that torsion rational. This is counterproductive in the context of point counting.

Vanilla is the most common and least complicated flavor of abelian varieties over finite fields. Heuristically, over large finite fields, randomly sampled abelian varieties are vanilla with overwhelming probability. Indeed, being vanilla is invariant in isogeny classes, and Howe and Zhu have shown in [14, Theorem 2] that the fraction of isogeny classes of g-dimensional abelian varieties over \(\mathbb{F}_{q}\) that are ordinary and absolutely simple tends to 1 as q → ∞. All absolutely simple ordinary abelian varieties are vanilla, except those whose endomorphism algebras contain roots of unity; but the number of such isogeny classes for fixed g is asymptotically negligible.

For full generality, we should also allow \(\deg f = 6\); the curve \(\mathcal{C}\) then has two points at infinity. This substantially complicates the formulæ without significantly modifying the algorithms or their asymptotic complexity, so we will not treat this case here.

With polynomial time estimates like these, who needs enemies?

See [24, Chapter 2, Section 2] for details on this subset. For point counting over large finite fields, it is enough to note that since the subset is Zariski open, randomly sampled Jacobians with real multiplication by \(\mathcal{O}_{F}\) have their RM invariants in this subset with overwhelming probability.

We emphasize that the subgroup \(\mathcal{A}[\mu ]\) depends on ι, but we have chosen to write \(\mathcal{A}[\mu ]\) instead of the more cumbersome \(\mathcal{A}[\iota (\mu )]\).

The polynomials H _μ, 3 do not appear there, but only G _μ is required to apply our results in §3.5.

Available from https://members.loria.fr/EMilio/modular-polynomials/.

Gaëtan Bisson, Romain Cosset, and Damien Robert, AVIsogenies: a library for computing isogenies between abelian varieties, http://avisogenies.gforge.inria.fr.

David G. Cantor, Computing in the Jacobian of a hyperelliptic curve , Math. Comp. 48 (1987), no. 177, 95–101.

Robert Carls, A generalized arithmetic geometric mean , Ph.D. thesis, University of Groningen, The Netherlands, 2004.

Jean-Marc Couveignes and Tony Ezome, Computing functions on Jacobians and their quotients , LMS J. Comput. Math. 18 (2015), no. 1, 555–577.CrossRefMATHMathSciNet

E. V. Flynn, The Jacobian and formal group of a curve of genus 2 over an arbitrary ground field , Math. Proc. Cambridge Philos. Soc. 107 (1990), no. 3, 425–441.CrossRefMATHMathSciNet

Pierrick Gaudry and Robert Harley, Counting points on hyperelliptic curves over finite fields , Algorithmic Number Theory, 4th International Symposium, ANTS-IV (Leiden, 2000) (W. Bosma, ed.), Lecture Notes in Computer Science, vol. 1838, Springer, Berlin, 2000, pp. 313–332.

Pierrick Gaudry, David Kohel, and Benjamin Smith, Counting points on genus 2 curves with real multiplication , Advances in Cryptology—ASIACRYPT 2011 (Dong Hoon Lee and Xiaoyun Wang, eds.), Lecture Notes in Computer Science, vol. 7073, Springer, Heidelberg, 2011, pp. 504–519.

Pierrick Gaudry and Eric Schost, Genus 2 point counting over prime fields , J. Symbolic Comput. 47 (2012), no. 4, 368–400.CrossRefMATHMathSciNet

Gerard van der Geer, Hilbert Modular Surfaces , Ergebnisse der Mathematik und ihrer Grenzgebiete (3), vol. 16, Springer, Berlin, 1988.

10.

David Grant, Formal groups in genus two , J. Reine Angew. Math. 411 (1990), 96–121.MATHMathSciNet

11.

Karl-Bernhard Gundlach, Die Bestimmung der Funktionen zur Hilbertschen Modulgruppe des Zahlkörpers \(\mathbb{Q}(\sqrt{5})\) , Math. Ann. 152 (1963), no. 3, 226–256.CrossRefMATHMathSciNet

12.

Michael C. Harrison, An extension of Kedlaya’s algorithm for hyperelliptic curves , J. Symbolic Comput. 47 (2012), no. 1, 89–101.

13.

David Harvey, Kedlaya’s algorithm in larger characteristic , Int. Math. Res. Not. IMRN (2007), no. 22, Art. ID rnm095, 29.

14.

Everett W. Howe and Hui June Zhu, On the existence of absolutely simple abelian varieties of a given dimension over an arbitrary field , J. Number Theory 92 (2002), no. 1, 139–163.

15.

Jun-ichi Igusa, On Siegel modular forms of genus two , Amer. J. Math. 84 (1962), 175–200.CrossRefMATHMathSciNet

16.

E. V. Flynn, Modular forms and projective invariants , Amer. J. Math. 89 (1967), 817–855.CrossRefMathSciNet

17.

Antoine Joux and Reynald Lercier, “Chinese & match”, an alternative to Atkin’s “match and sort” method used in the SEA algorithm , Math. Comp. 70 (2001), no. 234, 827–836.

18.

Kiran S. Kedlaya, Counting points on hyperelliptic curves using Monsky–Washnitzer cohomology, J. Ramanujan Math. Soc. 16 (2001), no. 4, 323–338.

19.

Serge Lang, Introduction to Algebraic and Abelian Functions, Graduate Texts in Mathematics, vol. 89, Springer-Verlag, New York, 1982.CrossRef

20.

E. V. Flynn, Algebraic Number Theory, Graduate Texts in Mathematics, vol. 16, Springer-Verlag, New York, 1986.

21.

Kristin Lauter, Michael Naehrig, and Tonghai Yang, Hilbert theta series and invariants of genus 2 curves , J. Number Theory 161 (2016), 146–174.CrossRefMATHMathSciNet

22.

Kristin Lauter and Tonghai Yang, Computing genus 2 curves from invariants on the Hilbert moduli space , J. Number Theory 131 (2011), no. 5, 936–958.CrossRefMATHMathSciNet

23.

Reynald Lercier, Algorithmique des courbes elliptiques dans les corps finis , Ph.D. thesis, École Polytechnique, Palaiseau, France, 1997.

24.

Chloe Martindale, Isogeny graphs, modular polynomials, and applications, Ph.D. thesis, Universiteit Leiden, 2017, in preparation.

25.

J.-F. Mestre, Lettre à Gaudry et Harley, https://webusers.imj-prg.fr/˜jean-francois.mestre/lettreGaudryHarley.ps, 2001.

26.

J.-F. Mestre, Algorithme pour compter des points de courbes en petite caractéristique et petit genre, https://webusers.imj-prg.fr/˜jean-francois.mestre/rennescrypto.ps, 2002, notes from a talk given at the Rennes cryptography seminar.

27.

Enea Milio, Calcul des polynômes modulaires en dimension 2 , Ph.D. thesis, Université de Bordeaux, December 2015.

28.

J.-F. Mestre, A quasi-linear time algorithm for computing modular polynomials in dimension 2 , LMS J. Comput. Math. 18 (2015), no. 1, 603–632.CrossRefMathSciNet

29.

J. S. Milne, Abelian varieties , Arithmetic Geometry (Storrs, 1984), Springer, New York, 1986, pp. 103–150.

30.

Rolf Müller, Hilbertsche Modulformen und Modulfunktionen zu \(\mathbb{Q}(\sqrt{5})\) , Arch. Math. (Basel) 45 (1985), no. 3, 239–251.CrossRefMATHMathSciNet

31.

J. Pila, Frobenius maps of abelian varieties and finding roots of unity in finite fields , Math. Comp. 55 (1990), no. 192, 745–763.CrossRefMATHMathSciNet

32.

Hans-Georg Rück, Abelian surfaces and Jacobian varieties over finite fields , Compositio Math. 76 (1990), no. 3, 351–366.MATHMathSciNet

33.

Takakazu Satoh, On p-adic point counting algorithms for elliptic curves over finite fields , Algorithmic Number Theory (Sydney, 2002) (C. Fieker and D. R. Kohel, eds.), Lecture Notes in Computer Science, vol. 2369, Springer, Berlin, 2002, pp. 43–66.

34.

René Schoof, Elliptic curves over finite fields and the computation of square roots mod p , Math. Comp. 44 (1985), no. 170, 483–494.MATHMathSciNet

35.

J. S. Milne, Counting points on elliptic curves over finite fields , J. Théor. Nombres Bordeaux 7 (1995), no. 1, 219–254.CrossRefMathSciNet

36.

Andrew V. Sutherland, On the evaluation of modular polynomials , ANTS X—Proceedings of the Tenth Algorithmic Number Theory Symposium (San Diego, 2012), Open Book Series, vol. 1, Mathematical Sciences Publishers, Berkeley, CA, 2013, pp. 531–555.

37.

Walter Tautz, Jaap Top, and Alain Verberkmoes, Explicit hyperelliptic curves with real multiplication and permutation polynomials , Canad. J. Math. 43 (1991), no. 5, 1055–1064.CrossRefMATHMathSciNet

38.

Lawrence C. Washington, Elliptic Curves: Number Theory and Cryptography , second ed., Discrete Mathematics and its Applications, vol. 50, Chapman & Hall/CRC, Boca Raton, FL, 2008.

Title: Isogenies for Point Counting on Genus Two Hyperelliptic Curves with Maximal Real Multiplication
Authors: Sean Ballentine
Aurore Guillevic
Elisa Lorenzo García
Chloe Martindale
Maike Massierer
Benjamin Smith
Jaap Top
Publisher: Springer International Publishing
Book: Algebraic Geometry for Coding Theory and Cryptography
Print ISBN: 978-3-319-63930-7

Electronic ISBN: 978-3-319-63931-4

Copyright Year: 2017
DOI: https://doi.org/10.1007/978-3-319-63931-4_3

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner