{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,4]],"date-time":"2026-06-04T04:01:59Z","timestamp":1780545719161,"version":"3.54.1"},"reference-count":23,"publisher":"American Mathematical Society (AMS)","issue":"260","license":[{"start":{"date-parts":[[2008,4,23]],"date-time":"2008-04-23T00:00:00Z","timestamp":1208908800000},"content-version":"am","delay-in-days":366,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"

\n Let\n \n \n \n C<\/mml:mi>\n C<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n be a curve of genus\n \n \n \n g<\/mml:mi>\n g<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n over a field\n \n \n \n k<\/mml:mi>\n k<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n . We describe probabilistic algorithms for addition and inversion of the classes of rational divisors in the Jacobian of\n \n \n \n C<\/mml:mi>\n C<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n . After a precomputation, which is done only once for the curve\n \n \n \n C<\/mml:mi>\n C<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n , the algorithms use only linear algebra in vector spaces of dimension at most\n \n \n \n \n O<\/mml:mi>\n (<\/mml:mo>\n g<\/mml:mi>\n log<\/mml:mi>\n \n \u2061\n \n <\/mml:mo>\n g<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n O(g \\log g)<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n , and so take\n \n \n \n \n O<\/mml:mi>\n (<\/mml:mo>\n \n g<\/mml:mi>\n \n 3<\/mml:mn>\n +<\/mml:mo>\n \n \u03f5\n \n <\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n O(g^{3 + \\epsilon })<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n field operations in\n \n \n \n k<\/mml:mi>\n k<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n , using Gaussian elimination. Using fast algorithms for the linear algebra, one can improve this time to\n \n \n \n \n O<\/mml:mi>\n (<\/mml:mo>\n \n g<\/mml:mi>\n \n 2.376<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n O(g^{2.376})<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n . This represents a significant improvement over the previous record of\n \n \n \n \n O<\/mml:mi>\n (<\/mml:mo>\n \n g<\/mml:mi>\n 4<\/mml:mn>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n O(g^4)<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n field operations (also after a precomputation) for general curves of genus\n \n \n \n g<\/mml:mi>\n g<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n .\n <\/p>","DOI":"10.1090\/s0025-5718-07-01989-8","type":"journal-article","created":{"date-parts":[[2007,7,26]],"date-time":"2007-07-26T07:46:03Z","timestamp":1185435963000},"page":"2213-2239","source":"Crossref","is-referenced-by-count":22,"title":["Asymptotically fast group operations on Jacobians of general curves"],"prefix":"10.1090","volume":"76","author":[{"given":"Kamal","family":"Khuri-Makdisi","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"14","published-online":{"date-parts":[[2007,4,23]]},"reference":[{"issue":"20","key":"1","doi-asserted-by":"publisher","first-page":"1005","DOI":"10.1155\/S1073792896000621","article-title":"A linear lower bound on the gonality of modular curves","author":"Abramovich, Dan","year":"1996","journal-title":"Internat. Math. Res. Notices","ISSN":"https:\/\/id.crossref.org\/issn\/1073-7928","issn-type":"print"},{"key":"2","series-title":"Addison-Wesley Series in Computer Science and Information Processing","volume-title":"The design and analysis of computer algorithms","author":"Aho, Alfred V.","year":"1975"},{"issue":"2","key":"3","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/S0001-8708(02)00024-5","article-title":"Abeliants and their application to an elementary construction of Jacobians","volume":"172","author":"Anderson, Greg W.","year":"2002","journal-title":"Adv. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0001-8708","issn-type":"print"},{"key":"4","series-title":"Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03338-8","volume-title":"Algebraic complexity theory","volume":"315","author":"B\u00fcrgisser, Peter","year":"1997","ISBN":"https:\/\/id.crossref.org\/isbn\/3540605827"},{"key":"5","unstructured":"[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 \\url{http:\/\/www.math.clemson.edu\/ sgao\/pub.html}"},{"key":"6","series-title":"Graduate Texts in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0913-3","volume-title":"Gr\\\"{o}bner bases","volume":"141","author":"Becker, Thomas","year":"1993","ISBN":"https:\/\/id.crossref.org\/isbn\/0387979719"},{"issue":"177","key":"7","doi-asserted-by":"publisher","first-page":"95","DOI":"10.2307\/2007876","article-title":"Computing in the Jacobian of a hyperelliptic curve","volume":"48","author":"Cantor, David G.","year":"1987","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"8","doi-asserted-by":"publisher","first-page":"453","DOI":"10.2307\/2372585","article-title":"The Jacobian variety of an algebraic curve","volume":"76","author":"Chow, Wei-Liang","year":"1954","journal-title":"Amer. J. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0002-9327","issn-type":"print"},{"issue":"3","key":"9","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/S0747-7171(08)80013-2","article-title":"Matrix multiplication via arithmetic progressions","volume":"9","author":"Coppersmith, Don","year":"1990","journal-title":"J. Symbolic Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"key":"10","isbn-type":"print","first-page":"187","article-title":"Primary decomposition: algorithms and comparisons","author":"Decker, Wolfram","year":"1999","ISBN":"https:\/\/id.crossref.org\/isbn\/3540646701"},{"issue":"3","key":"11","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1006\/jsco.1999.0308","article-title":"Efficient decomposition of associative algebras over finite fields","volume":"29","author":"Eberly, W.","year":"2000","journal-title":"J. Symbolic Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"key":"12","series-title":"Wiley Classics Library","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032527","volume-title":"Principles of algebraic geometry","author":"Griffiths, Phillip","year":"1994","ISBN":"https:\/\/id.crossref.org\/isbn\/0471050598"},{"key":"13","series-title":"Graduate Texts in Mathematics, No. 52","isbn-type":"print","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-3849-0","volume-title":"Algebraic geometry","author":"Hartshorne, Robin","year":"1977","ISBN":"https:\/\/id.crossref.org\/isbn\/0387902449"},{"key":"14","unstructured":"[Hes99] Florian Hess, Zur Divisorenklassengruppenberechnung in globalen Funktionenk\u00f6rpern, Ph.D. thesis, Technische Universit\u00e4t Berlin, 1999, may be downloaded from the web at \\url{http:\/\/www.math.tu-berlin.de\/ kant\/publications\/diss\/diss_{F}H.ps.gz}"},{"issue":"4","key":"15","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1006\/jsco.2001.0513","article-title":"Computing Riemann-Roch spaces in algebraic function fields and related topics","volume":"33","author":"Hess, F.","year":"2002","journal-title":"J. Symbolic Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"issue":"6","key":"16","doi-asserted-by":"publisher","first-page":"519","DOI":"10.1006\/jsco.1994.1063","article-title":"Efficient algorithms for the Riemann-Roch problem and for addition in the Jacobian of a curve","volume":"18","author":"Huang, Ming-Deh","year":"1994","journal-title":"J. Symbolic Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"issue":"3","key":"17","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1006\/jsco.2002.0560","article-title":"The calculation of radical ideals in positive characteristic","volume":"34","author":"Kemper, Gregor","year":"2002","journal-title":"J. Symbolic Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"issue":"245","key":"18","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1090\/S0025-5718-03-01567-9","article-title":"Linear algebra algorithms for divisors on an algebraic curve","volume":"73","author":"Khuri-Makdisi, Kamal","year":"2004","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"19","unstructured":"[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 \\url{http:\/\/arxiv.org\/abs\/math.NT\/0409209v2}"},{"key":"20","isbn-type":"print","first-page":"500","article-title":"A sampling of vector bundle techniques in the study of linear series","author":"Lazarsfeld, Robert","year":"1989","ISBN":"https:\/\/id.crossref.org\/isbn\/9971509024"},{"key":"21","unstructured":"[PARI] The PARI Group, Bordeaux, PARI\/GP, may be downloaded from the web at the URL \\url{http:\/\/pari.math.u-bordeaux.fr\/}"},{"key":"22","unstructured":"[Ste04] W. Stein, Modular Forms Database, \\url{http:\/\/modular.math.washington.edu\/Tables}"},{"key":"23","isbn-type":"print","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1007\/3-540-58691-1_60","article-title":"Computing in the Jacobian of a plane algebraic curve","author":"Volcheck, Emil J.","year":"1994","ISBN":"https:\/\/id.crossref.org\/isbn\/3540586911"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2007-76-260\/S0025-5718-07-01989-8\/S0025-5718-07-01989-8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2007-76-260\/S0025-5718-07-01989-8\/S0025-5718-07-01989-8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T15:03:56Z","timestamp":1776783836000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2007-76-260\/S0025-5718-07-01989-8\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,4,23]]},"references-count":23,"journal-issue":{"issue":"260","published-print":{"date-parts":[[2007,10]]}},"alternative-id":["S0025-5718-07-01989-8"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-07-01989-8","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2007,4,23]]}}}