Computing in Picard groups of projective curves over finite fields
HTML articles powered by AMS MathViewer
- by Peter Bruin
- Math. Comp. 82 (2013), 1711-1756
- DOI: https://doi.org/10.1090/S0025-5718-2012-02650-0
- Published electronically: September 14, 2012
- PDF | Request permission
Abstract:
We give algorithms for computing with divisors on projective curves over finite fields, and with their Jacobians, using the algorithmic representation of projective curves developed by Khuri-Makdisi. We show that various desirable operations can be performed efficiently in this setting: decomposing divisors into prime divisors; computing pull-backs and push-forwards of divisors under finite morphisms, and hence Picard and Albanese maps on Jacobians; generating uniformly random divisors and points on Jacobians; computing Frobenius maps; and finding a basis for the $l$-torsion of the Picard group for prime numbers $l$ different from the characteristic of the base field.References
- L. M. Adleman and H. W. Lenstra, Jr., Finding irreducible polynomials over finite fields. In: Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing (Berkeley, CA, 1986), 350–355. Association for Computing Machinery, New York, 1986.
- J. G. Bosman, Explicit computations with modular Galois representations. Proefschrift (Ph.D. thesis), Universiteit Leiden, 2008.
- P. J. Bruin, Modular curves, Arakelov theory, algorithmic applications. Proefschrift (Ph.D. thesis), Universiteit Leiden, 2010.
- G. Castelnuovo, Sui multipli di una serie lineare di gruppi di punti appartenente ad una curva algebrica. Rendiconti del Circolo Matematico di Palermo 7 (1893), 89–110. (= Memorie scelte, 95–113. Zanichelli, Bologna, 1937.)
- 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
- C. Diem, On arithmetic and the discrete logarithm problem in class groups of curves. Habilitationsschrift, Universität Leipzig, 2008.
- Claus Diem, On the discrete logarithm problem in class groups of curves, Math. Comp. 80 (2011), no. 273, 443–475. MR 2728990, DOI 10.1090/S0025-5718-2010-02281-1
- W. Eberly and M. Giesbrecht, Efficient decomposition of associative algebras over finite fields, J. Symbolic Comput. 29 (2000), no. 3, 441–458. MR 1751390, DOI 10.1006/jsco.1999.0308
- S. J. Edixhoven and J.-M. Couveignes (with R. S. de Jong, F. Merkl and J. G. Bosman), Computational Aspects of Modular Forms and Galois Representations. Annals of Mathematics Studies 176, Princeton University Press, 2011.
- 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
- Robin Hartshorne, Algebraic geometry, Graduate Texts in Mathematics, No. 52, Springer-Verlag, New York-Heidelberg, 1977. MR 463157
- 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
- Robert Lazarsfeld, A sampling of vector bundle techniques in the study of linear series, Lectures on Riemann surfaces (Trieste, 1987) World Sci. Publ., Teaneck, NJ, 1989, pp. 500–559. MR 1082360
- Arthur Mattuck, Symmetric products and Jacobians, Amer. J. Math. 83 (1961), 189–206. MR 142553, DOI 10.2307/2372727
- David Mumford, Varieties defined by quadratic equations, Questions on Algebraic Varieties (C.I.M.E., III Ciclo, Varenna, 1969) Centro Internazionale Matematico Estivo (C.I.M.E.), Ed. Cremonese, Rome, 1970, pp. 29–100. MR 282975
- Michael O. Rabin, Probabilistic algorithms in finite fields, SIAM J. Comput. 9 (1980), no. 2, 273–280. MR 568814, DOI 10.1137/0209024
- Edward F. Schaefer, A new proof for the non-degeneracy of the Frey-Rück pairing and a connection to isogenies over the base field, Computational aspects of algebraic curves, Lecture Notes Ser. Comput., vol. 13, World Sci. Publ., Hackensack, NJ, 2005, pp. 1–12. MR 2181869, DOI 10.1142/9789812701640_{0}001
- Théorie des topos et cohomologie étale des schémas. Tome 3, Lecture Notes in Mathematics, Vol. 305, Springer-Verlag, Berlin-New York, 1973 (French). Séminaire de Géométrie Algébrique du Bois-Marie 1963–1964 (SGA 4); Dirigé par M. Artin, A. Grothendieck et J. L. Verdier. Avec la collaboration de P. Deligne et B. Saint-Donat. MR 354654
- William Stein, Modular forms, a computational approach, Graduate Studies in Mathematics, vol. 79, American Mathematical Society, Providence, RI, 2007. With an appendix by Paul E. Gunnells. MR 2289048, DOI 10.1090/gsm/079
Bibliographic Information
- Peter Bruin
- Affiliation: Institut für Mathematik, Universität Zürich, Winterthurerstrasse 190, CH-8057 Zürich
- Email: peter.bruin@math.uzh.ch
- Received by editor(s): February 4, 2011
- Received by editor(s) in revised form: November 2, 2011
- Published electronically: September 14, 2012
- Additional Notes: This paper evolved from one of the chapters of the author’s thesis [Modular curves, Arakelov theory, algorithmic applications, Proefschrift, Universiteit Leiden, 2010], the research for which was supported by the Netherlands Organisation for Scientific Research (NWO)
- © Copyright 2012
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Math. Comp. 82 (2013), 1711-1756
- MSC (2010): Primary 11G20, 11Y16, 14Q05
- DOI: https://doi.org/10.1090/S0025-5718-2012-02650-0
- MathSciNet review: 3042583