{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,4]],"date-time":"2026-06-04T03:46:59Z","timestamp":1780544819917,"version":"3.54.1"},"reference-count":14,"publisher":"American Mathematical Society (AMS)","issue":"245","license":[{"start":{"date-parts":[[2004,7,7]],"date-time":"2004-07-07T00:00:00Z","timestamp":1089158400000},"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 We use an embedding of the symmetric\n \n \n \n d<\/mml:mi>\n d<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n th power of any algebraic curve\n \n \n \n C<\/mml:mi>\n C<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n of genus\n \n \n \n g<\/mml:mi>\n g<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n into a Grassmannian space to give algorithms for working with divisors on\n \n \n \n C<\/mml:mi>\n C<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n , using only linear algebra in vector spaces of dimension\n \n \n \n \n O<\/mml:mi>\n (<\/mml:mo>\n g<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n O(g)<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n , and matrices of size\n \n \n \n \n O<\/mml:mi>\n (<\/mml:mo>\n \n g<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n )<\/mml:mo>\n \n \u00d7\n \n <\/mml:mo>\n O<\/mml:mi>\n (<\/mml:mo>\n g<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n O(g^2)\\times O(g)<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n . When the base field\n \n \n \n k<\/mml:mi>\n k<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n is finite, or if\n \n \n \n C<\/mml:mi>\n C<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n has a rational point over\n \n \n \n k<\/mml:mi>\n k<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n , these give algorithms for working on the Jacobian of\n \n \n \n C<\/mml:mi>\n C<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n that require\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, arising from the Gaussian elimination. Our point of view is strongly geometric, and our representation of points on the Jacobian is fairly simple to deal with; in particular, none of our algorithms involves arithmetic with polynomials. We note that our algorithms have the same asymptotic complexity for general curves as the more algebraic algorithms in Florian Hess\u2019 1999 Ph.D. thesis, which works with function fields as extensions of\n \n \n \n \n k<\/mml:mi>\n [<\/mml:mo>\n x<\/mml:mi>\n ]<\/mml:mo>\n <\/mml:mrow>\n k[x]<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n . However, for special classes of curves, Hess\u2019 algorithms are asymptotically more efficient than ours, generalizing other known efficient algorithms for special classes of curves, such as hyperelliptic curves (Cantor 1987), superelliptic curves (Galbraith, Paulus, and Smart 2002), and\n \n \n \n \n C<\/mml:mi>\n \n a<\/mml:mi>\n b<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msub>\n C_{ab}<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n curves (Harasawa and Suzuki 2000); in all those cases, one can attain a complexity of\n \n \n \n \n O<\/mml:mi>\n (<\/mml:mo>\n \n g<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n O(g^2)<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n .\n <\/p>","DOI":"10.1090\/s0025-5718-03-01567-9","type":"journal-article","created":{"date-parts":[[2003,10,10]],"date-time":"2003-10-10T19:11:14Z","timestamp":1065813074000},"page":"333-357","source":"Crossref","is-referenced-by-count":26,"title":["Linear algebra algorithms for divisors on an algebraic curve"],"prefix":"10.1090","volume":"73","author":[{"given":"Kamal","family":"Khuri-Makdisi","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"14","published-online":{"date-parts":[[2003,7,7]]},"reference":[{"key":"1","series-title":"Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-5323-3","volume-title":"Geometry of algebraic curves. Vol. I","volume":"267","author":"Arbarello, E.","year":"1985","ISBN":"https:\/\/id.crossref.org\/isbn\/0387909974"},{"key":"2","isbn-type":"print","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1007\/3-540-58691-1_39","article-title":"A subexponential algorithm for discrete logarithms over the rational subgroup of the Jacobians of large genus hyperelliptic curves over finite fields","author":"Adleman, Leonard M.","year":"1994","ISBN":"https:\/\/id.crossref.org\/isbn\/3540586911"},{"key":"3","series-title":"Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)]","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-51438-8","volume-title":"N\\'{e}ron models","volume":"21","author":"Bosch, Siegfried","year":"1990","ISBN":"https:\/\/id.crossref.org\/isbn\/3540505873"},{"issue":"177","key":"4","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":"5","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"},{"issue":"237","key":"6","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1090\/S0025-5718-00-01297-7","article-title":"Arithmetic on superelliptic curves","volume":"71","author":"Galbraith, S. D.","year":"2002","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"7","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":"8","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}."},{"key":"9","doi-asserted-by":"crossref","unstructured":"[Hes02] Florian Hess, Computing Riemann-Roch spaces in algebraic function fields and related topics, J. Symbolic Comput. 33 (2002), no. 4, 425\u2013445.","DOI":"10.1006\/jsco.2001.0513"},{"issue":"6","key":"10","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"},{"key":"11","isbn-type":"print","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1007\/10722028_21","article-title":"Fast Jacobian group arithmetic on \ud835\udc36_{\ud835\udc4e\ud835\udc4f} curves","author":"Harasawa, Ryuichi","year":"2000","ISBN":"https:\/\/id.crossref.org\/isbn\/3540676953"},{"key":"12","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":"13","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-8655-1","volume-title":"Arithmetic geometry","year":"1986","ISBN":"https:\/\/id.crossref.org\/isbn\/0387963111"},{"key":"14","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\/2004-73-245\/S0025-5718-03-01567-9\/S0025-5718-03-01567-9.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2004-73-245\/S0025-5718-03-01567-9\/S0025-5718-03-01567-9.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T13:38:35Z","timestamp":1776778715000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2004-73-245\/S0025-5718-03-01567-9\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,7,7]]},"references-count":14,"journal-issue":{"issue":"245","published-print":{"date-parts":[[2004,1]]}},"alternative-id":["S0025-5718-03-01567-9"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-03-01567-9","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":[[2003,7,7]]}}}