Hensel-lifting torsion points on Jacobians and Galois representations

Mascot, Nicolas

doi:10.1090/mcom/3484

Hensel-lifting torsion points on Jacobians and Galois representations
HTML articles powered by AMS MathViewer

by Nicolas Mascot HTML | PDF

Math. Comp. 89 (2020), 1417-1455 Request permission

Abstract:

Let $\rho$ be a mod $\ell$ Galois representation. We show how to compute $\rho$ explicitly, given the characteristic polynomial of the image of the Frobenius at one prime $p$ and a curve $C$ whose Jacobian contains $\rho$ in its $\ell$-torsion. The main ingredient is a method to $p$-adically lift torsion points on a Jacobian in the framework of Makdisi’s algorithms.

References

Simon Abelard, Pierrick Gaudry, and Pierre-Jean Spaenlehauer, Improved complexity bounds for counting points on hyperelliptic curves, Found. Comput. Math. 19 (2019), no. 3, 591–621. MR 3958802, DOI 10.1007/s10208-018-9392-1
F. Bergeron, J. Berstel, and S. Brlek, Efficient computation of addition chains, J. Théor. Nombres Bordeaux 6 (1994), no. 1, 21–38. MR 1305286
Peter Bruin, Computing in Picard groups of projective curves over finite fields, Math. Comp. 82 (2013), no. 283, 1711–1756. MR 3042583, DOI 10.1090/S0025-5718-2012-02650-0
H. Cohen, G. Frey, R. Avanzi, C. Doche, T. Lange, K. Nguyen, F. Vercauteren, eds., Handbook of elliptic and hyperelliptic curve cryptography, CRC press, 2005
Tim Dokchitser and Vladimir Dokchitser, Identifying Frobenius elements in Galois groups, Algebra Number Theory 7 (2013), no. 6, 1325–1352. MR 3107565, DOI 10.2140/ant.2013.7.1325
Noam D. Elkies, The Klein quartic in number theory, The eightfold way, Math. Sci. Res. Inst. Publ., vol. 35, Cambridge Univ. Press, Cambridge, 1999, pp. 51–101. MR 1722413
Gerhard Frey and Hans-Georg Rück, A remark concerning $m$-divisibility and the discrete logarithm in the divisor class group of curves, Math. Comp. 62 (1994), no. 206, 865–874. MR 1218343, DOI 10.1090/S0025-5718-1994-1218343-6
The GAP Group, GAP – Groups, Algorithms, and Programming, Version 4.9.2; 2018. (https://www.gap-system.org)
N. Mascot, Github repository, https://github.com/nmascot/LiftTors.
F. Hess, Computing Riemann-Roch spaces in algebraic function fields and related topics, J. Symbolic Comput. 33 (2002), no. 4, 425–445. MR 1890579, DOI 10.1006/jsco.2001.0513
John A. Howell, Spans in the module $(Z_m)^s$, Linear and Multilinear Algebra 19 (1986), no. 1, 67–77. MR 835631, DOI 10.1080/03081088608817705
Kamal Khuri-Makdisi, Linear algebra algorithms for divisors on an algebraic curve, Math. Comp. 73 (2004), no. 245, 333–357. MR 2034126, DOI 10.1090/S0025-5718-03-01567-9
Kamal Khuri-Makdisi, Asymptotically fast group operations on Jacobians of general curves, Math. Comp. 76 (2007), no. 260, 2213–2239. MR 2336292, DOI 10.1090/S0025-5718-07-01989-8
The LMFDB Collaboration, The L-functions and Modular Forms Database, http://www.lmfdb.org
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
N. Mascot, Personal web page, https://staff.aub.edu.lb/~nm116/.
Nicolas Mascot, Computing modular Galois representations, Rend. Circ. Mat. Palermo (2) 62 (2013), no. 3, 451–476. MR 3118315, DOI 10.1007/s12215-013-0136-4
Nicolas Mascot, Certification of modular Galois representations, Math. Comp. 87 (2018), no. 309, 381–423. MR 3716200, DOI 10.1090/mcom/3215
Nicolas Mascot, Companion forms and explicit computation of $\rm PGL_2$ number fields with very little ramification, J. Algebra 509 (2018), 476–506. MR 3812211, DOI 10.1016/j.jalgebra.2017.10.027
Mascot, Nicolas, Explicit computation of a Galois representation attached to an eigenform over $\operatorname {SL}_3$ from the $\operatorname {H}^2$ étale of a surface, ArXiv preprint 1810.05885 (2019).
Victor S. Miller, The Weil pairing, and its efficient calculation, J. Cryptology 17 (2004), no. 4, 235–261. MR 2090556, DOI 10.1007/s00145-004-0315-8
A. M. Odlyzko, Bounds for discriminants and related estimates for class numbers, regulators and zeros of zeta functions: a survey of recent results, Sém. Théor. Nombres Bordeaux (2) 2 (1990), no. 1, 119–141 (English, with French summary). MR 1061762
The PARI Group, PARI/GP development version 2.10.0, Bordeaux, 2018, http://pari.math.u-bordeaux.fr/
Ravnshøj, Christian Robenhagen, Generators of Jacobians of Genus Two Curves, IACR Cryptology ePrint Archive 2008: 70, https://eprint.iacr.org/2007/150.pdf.
Joseph H. Silverman, The arithmetic of elliptic curves, 2nd ed., Graduate Texts in Mathematics, vol. 106, Springer, Dordrecht, 2009. MR 2514094, DOI 10.1007/978-0-387-09494-6
Arne Storjohann and Thom Mulders, Fast algorithms for linear algebra modulo $N$, Algorithms—ESA ’98 (Venice), Lecture Notes in Comput. Sci., vol. 1461, Springer, Berlin, 1998, pp. 139–150. MR 1683348, DOI 10.1007/3-540-68530-8_{1}2