Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Asymptotically fast group operations on Jacobians of general curves

Author: Kamal Khuri-Makdisi
Journal: Math. Comp. 76 (2007), 2213-2239
MSC (2000): Primary 11Y16, 14Q05, 14H40, 11G20
Published electronically: April 23, 2007
MathSciNet review: 2336292
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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

  • [Abr96] Dan Abramovich, A linear lower bound on the gonality of modular curves, Internat. Math. Res. Notices (1996), no. 20, 1005-1011. MR 1422373 (98b:11063)
  • [AHU75] Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman, The design and analysis of computer algorithms, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. MR 0413592 (54:1706)
  • [And02] Greg W. Anderson, Abeliants and their application to an elementary construction of Jacobians, Adv. Math. 172 (2002), no. 2, 169-205. MR 1942403 (2004c:14056)
  • [BCS97] 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. MR 1440179 (99c:68002)
  • [BG04] 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
  • [BW93] Thomas Becker and Volker Weispfenning, Gröbner bases, Graduate Texts in Mathematics, vol. 141, Springer-Verlag, New York, 1993. MR 1213453 (95e:13018)
  • [Can87] David G. Cantor, Computing in the Jacobian of a hyperelliptic curve, Math. Comp. 48 (1987), no. 177, 95-101. MR 866101 (88f:11118)
  • [Cho54] Wei-Liang Chow, The Jacobian variety of an algebraic curve, Amer. J. Math. 76 (1954), 453-476. MR 0061421 (15:823a)
  • [CW90] Don Coppersmith and Shmuel Winograd, Matrix multiplication via arithmetic progressions, J. Symbolic Comput. 9 (1990), no. 3, 251-280. MR 1056627 (91i:68058)
  • [DGP99] 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 (99m:13049)
  • [EG00] W. Eberly and M. Giesbrecht, Efficient decomposition of associative algebras over finite fields, J. Symbolic Comput. 29 (2000), no. 3, 441-458. MR 1751390 (2001a:16079)
  • [GH94] Phillip Griffiths and Joseph Harris, Principles of algebraic geometry, Wiley Classics Library (reprint of 1978 edition), John Wiley & Sons Inc., New York, 1994. MR 1288523 (95d:14001)
  • [Har77] Robin Hartshorne, Algebraic geometry, Springer-Verlag, New York, 1977, Graduate Texts in Mathematics, No. 52. MR 0463157 (57:3116)
  • [Hes99] Florian Hess, Zur Divisorenklassengruppenberechnung in globalen Funktionenkörpern, Ph.D. thesis, Technische Universität Berlin, 1999, may be downloaded from the web at
  • [Hes02] -, Computing Riemann-Roch spaces in algebraic function fields and related topics, J. Symbolic Comput. 33 (2002), no. 4, 425-445. MR 1890579 (2003j:14032)
  • [HI94] 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 (96h:14077)
  • [Kem02] Gregor Kemper, The calculation of radical ideals in positive characteristic, J. Symbolic Comput. 34 (2002), no. 3, 229-238. MR 1935080 (2003j:13039)
  • [KM04a] -, Linear algebra algorithms for divisors on an algebraic curve, Math. Comp. 73 (2004), no. 245, 333-357 (electronic), math.NT/0105182. MR 2034126 (2005a:14081)
  • [KM04b] 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
  • [Laz89] Robert Lazarsfeld, A sampling of vector bundle techniques in the study of linear series, Lectures on Riemann surfaces (Trieste, 1987) (M. Cornalba, X. Gomez-Mont, and A. Verjovsky, eds.), World Sci. Publishing, Teaneck, NJ, 1989, pp. 500-559. MR 1082360 (92f:14006)
  • [PARI] The PARI Group, Bordeaux, PARI/GP, may be downloaded from the web at the URL
  • [Ste04] W. Stein, Modular Forms Database,
  • [Vol94] Emil J. Volcheck, Computing in the Jacobian of a plane algebraic curve, Algorithmic number theory ``ANTS-I'' (Ithaca, NY, 1994) (Leonard M. Adleman and Ming-Deh Huang, eds.), Lecture Notes in Comput. Sci., vol. 877, Springer, Berlin, 1994, pp. 221-233. MR 1322725 (96a:14033)

Similar Articles

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

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

Additional Information

Kamal Khuri-Makdisi
Affiliation: Mathematics Department and Center for Advanced Mathematical Sciences, American University of Beirut, Bliss Street, Beirut, Lebanon

Received by editor(s): July 3, 2006
Received by editor(s) in revised form: August 20, 2006
Published electronically: April 23, 2007
Article copyright: © Copyright 2007 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society