Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Computing in Picard groups of projective curves over finite fields

Author: Peter Bruin
Journal: Math. Comp. 82 (2013), 1711-1756
MSC (2010): Primary 11G20, 11Y16, 14Q05
Published electronically: September 14, 2012
MathSciNet review: 3042583
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. 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.
  • 2. J. G. BOSMAN, Explicit computations with modular Galois representations. Proefschrift (Ph.D.thesis), Universiteit Leiden, 2008.
  • 3. P. J. BRUIN, Modular curves, Arakelov theory, algorithmic applications. Proefschrift (Ph.D.thesis), Universiteit Leiden, 2010.
  • 4. 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.)
  • 5. J.-M. COUVEIGNES, Linearizing torsion classes in the Picard group of algebraic curves over finite fields. Journal of Algebra 321 (2009), 2085-2118. MR 2501511 (2010e:14019)
  • 6. C. DIEM, On arithmetic and the discrete logarithm problem in class groups of curves. Habilitationsschrift, Universität Leipzig, 2008.
  • 7. C. DIEM, On the discrete logarithm problem in class groups of curves. Mathematics of Computation 80 (2011), 443-475. MR 2728990 (2011j:11242)
  • 8. W. EBERLY and M. GIESBRECHT, Efficient decomposition of associative algebras over finite fields. Journal of Symbolic Computation 29 (2000), 441-458. MR 1751390 (2001a:16079)
  • 9. 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.
  • 10. G. FREY and H.-G. R¨UCK, A remark concerning $ m$-divisibility and the discrete logarithm in the divisor class group of curves. Mathematics of Computation 62 (1994), 865-874. MR 1218343 (94h:11056)
  • 11. R. HARTSHORNE, Algebraic Geometry. Graduate Texts in Mathematics 52, Springer-Verlag, New York, 1977. MR 0463157 (57:3116)
  • 12. K. KHURI-MAKDISI, Linear algebra algorithms for divisors on an algebraic curve. Mathematics of Computation 73 (2004), no. 245, 333-357. MR 2034126 (2005a:14081)
  • 13. K. KHURI-MAKDISI, Asymptotically fast group operations on Jacobians of general curves. Mathematics of Computation 76 (2007), no. 260, 2213-2239. MR 2336292 (2009a:14072)
  • 14. R. LAZARSFELD, A sampling of vector bundle techniques in the study of linear series. In: M. CORNALBA, X. GOMEZ-MONT and A. VERJOVSKY (editors), Lectures on Riemann Surfaces (Trieste, 1987), 500-559. World Scientific Publishing, Teaneck, NJ, 1989. MR 1082360 (92f:14006)
  • 15. A. MATTUCK, Symmetric products and Jacobians. American Journal of Mathematics 83 (1961), no. 1, 189-206. MR 0142553 (26:122)
  • 16. D. MUMFORD, Varieties defined by quadratic equations. With an appendix by G. KEMPF. In: Questions on Algebraic Varieties (Centro Internationale Matematico Estivo, $ 3^{\rm o}$ ciclo, Varenna, 1969), 29-100. Edizioni Cremonese, Roma, 1970. MR 0282975 (44:209)
  • 17. M. O. RABIN, Probabilistic algorithms in finite fields. SIAM Journal on Computing 9 (1980), no. 2, 273-280. MR 568814 (81g:12002)
  • 18. E. F. SCHAEFER, A new proof for the non-degeneracy of the Frey-Rück pairing and a connection to isogenies over the base field. In: T. SHASKA (editor), Computational Aspects of Algebraic Curves (Conference held at the University of Idaho, 2005), 1-12. Lecture Notes Series in Computing 13, World Scientific Publishing, Hackensack, NJ, 2005. MR 2181869 (2006i:14019)
  • 19. Théorie des topos et cohomologie étale des schémas (SGA 4). Tome 3 (exposés IX à XIX). Séminaire de Géométrie Algébrique du Bois-Marie 1963-1964, dirigé par M. ARTIN, A. GROTHENDIECK et J.-L. VERDIER, avec la collaboration de P. DELIGNE et B. SAINT-DONAT. Lecture Notes in Mathematics 305, Springer-Verlag, Berlin/Heidelberg/New York, 1973. MR 0354654 (50:7132)
  • 20. W. A. STEIN, Modular Forms, a Computational Approach. With an appendix by P. E. GUNNELLS. Graduate Studies in Mathematics 79, American Mathematical Society, Providence, RI, 2007. MR 2289048 (2008d:11037)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11G20, 11Y16, 14Q05

Retrieve articles in all journals with MSC (2010): 11G20, 11Y16, 14Q05

Additional Information

Peter Bruin
Affiliation: Institut für Mathematik, Universität Zürich, Winterthurerstrasse 190, CH-8057 Zürich

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)
Article copyright: © Copyright 2012 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society