## Computing in Picard groups of projective curves over finite fields

HTML articles powered by AMS MathViewer

- by Peter Bruin PDF
- Math. Comp.
**82**(2013), 1711-1756 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**0463157** - 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) Edizioni Cremonese, Rome, 1970, pp. 29–100. MR**0282975** - 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**0354654**- 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

## Additional 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