## Asymptotically fast group operations on Jacobians of general curves

HTML articles powered by AMS MathViewer

- by Kamal Khuri-Makdisi PDF
- Math. Comp.
**76**(2007), 2213-2239 Request permission

## Abstract:

Let $C$ be a curve of genus $g$ over a field $k$. We describe probabilistic algorithms for addition and inversion of the classes of rational divisors in the Jacobian of $C$. After a precomputation, which is done only once for the curve $C$, the algorithms use only linear algebra in vector spaces of dimension at most $O(g \log g)$, and so take $O(g^{3 + \epsilon })$ field operations in $k$, using Gaussian elimination. Using fast algorithms for the linear algebra, one can improve this time to $O(g^{2.376})$. This represents a significant improvement over the previous record of $O(g^4)$ field operations (also after a precomputation) for general curves of genus $g$.## References

- Dan Abramovich,
*A linear lower bound on the gonality of modular curves*, Internat. Math. Res. Notices**20**(1996), 1005–1011. MR**1422373**, DOI 10.1155/S1073792896000621 - Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman,
*The design and analysis of computer algorithms*, Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Second printing. MR**0413592** - Greg W. Anderson,
*Abeliants and their application to an elementary construction of Jacobians*, Adv. Math.**172**(2002), no. 2, 169–205. MR**1942403**, DOI 10.1016/S0001-8708(02)00024-5 - Peter Bürgisser, Michael Clausen, and M. Amin Shokrollahi,
*Algebraic complexity theory*, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 315, Springer-Verlag, Berlin, 1997. With the collaboration of Thomas Lickteig. MR**1440179**, DOI 10.1007/978-3-662-03338-8 - Joel Brawley and Shuhong Gao,
*On density of primitive elements for field extensions*, 2004 preprint, may be electronically downloaded from the web at the URL http://www.math.clemson.edu/~sgao/pub.html - Thomas Becker and Volker Weispfenning,
*Gröbner bases*, Graduate Texts in Mathematics, vol. 141, Springer-Verlag, New York, 1993. A computational approach to commutative algebra; In cooperation with Heinz Kredel. MR**1213453**, DOI 10.1007/978-1-4612-0913-3 - David G. Cantor,
*Computing in the Jacobian of a hyperelliptic curve*, Math. Comp.**48**(1987), no. 177, 95–101. MR**866101**, DOI 10.1090/S0025-5718-1987-0866101-0 - Wei-Liang Chow,
*The Jacobian variety of an algebraic curve*, Amer. J. Math.**76**(1954), 453–476. MR**61421**, DOI 10.2307/2372585 - Don Coppersmith and Shmuel Winograd,
*Matrix multiplication via arithmetic progressions*, J. Symbolic Comput.**9**(1990), no. 3, 251–280. MR**1056627**, DOI 10.1016/S0747-7171(08)80013-2 - Wolfram Decker, Gert-Martin Greuel, and Gerhard Pfister,
*Primary decomposition: algorithms and comparisons*, Algorithmic algebra and number theory (Heidelberg, 1997) Springer, Berlin, 1999, pp. 187–220. MR**1672046** - 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 - Phillip Griffiths and Joseph Harris,
*Principles of algebraic geometry*, Wiley Classics Library, John Wiley & Sons, Inc., New York, 1994. Reprint of the 1978 original. MR**1288523**, DOI 10.1002/9781118032527 - Robin Hartshorne,
*Algebraic geometry*, Graduate Texts in Mathematics, No. 52, Springer-Verlag, New York-Heidelberg, 1977. MR**0463157** - Florian Hess,
*Zur Divisorenklassengruppenberechnung in globalen Funktionenkörpern*, Ph.D. thesis, Technische Universität Berlin, 1999, may be downloaded from the web at http://www.math.tu-berlin.de/~kant/publications/diss/diss_FH.ps.gz - 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 - Ming-Deh Huang and Doug Ierardi,
*Efficient algorithms for the Riemann-Roch problem and for addition in the Jacobian of a curve*, J. Symbolic Comput.**18**(1994), no. 6, 519–539. MR**1334660**, DOI 10.1006/jsco.1994.1063 - Gregor Kemper,
*The calculation of radical ideals in positive characteristic*, J. Symbolic Comput.**34**(2002), no. 3, 229–238. MR**1935080**, DOI 10.1006/jsco.2002.0560 - 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 (previous draft, version 2)*, 2004 preprint, may be electronically downloaded from the web at the URL http://arxiv.org/abs/math.NT/0409209v2 - 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** - The PARI Group, Bordeaux,
*PARI/GP*, may be downloaded from the web at the URL http://pari.math.u-bordeaux.fr/ - W. Stein,
*Modular Forms Database*, http://modular.math.washington.edu/Tables - Emil J. Volcheck,
*Computing in the Jacobian of a plane algebraic curve*, Algorithmic number theory (Ithaca, NY, 1994) Lecture Notes in Comput. Sci., vol. 877, Springer, Berlin, 1994, pp. 221–233. MR**1322725**, DOI 10.1007/3-540-58691-1_{6}0

## Additional Information

**Kamal Khuri-Makdisi**- Affiliation: Mathematics Department and Center for Advanced Mathematical Sciences, American University of Beirut, Bliss Street, Beirut, Lebanon
- MR Author ID: 610136
- Email: kmakdisi@aub.edu.lb
- Received by editor(s): July 3, 2006
- Received by editor(s) in revised form: August 20, 2006
- Published electronically: April 23, 2007
- © Copyright 2007
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication. - Journal: Math. Comp.
**76**(2007), 2213-2239 - MSC (2000): Primary 11Y16, 14Q05, 14H40, 11G20
- DOI: https://doi.org/10.1090/S0025-5718-07-01989-8
- MathSciNet review: 2336292