{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T15:56:11Z","timestamp":1776873371075,"version":"3.51.2"},"reference-count":28,"publisher":"American Mathematical Society (AMS)","issue":"325","license":[{"start":{"date-parts":[[2021,2,18]],"date-time":"2021-02-18T00:00:00Z","timestamp":1613606400000},"content-version":"am","delay-in-days":366,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"funder":[{"DOI":"10.13039\/100008990","name":"Universit\u00c3\u00a9 de Lorraine","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100008990","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100012950","name":"Institut national de recherche en informatique et en automatique","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100012950","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004794","name":"Centre National de la Recherche Scientifique","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100004794","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100012950","name":"Institut national de recherche en informatique et en automatique","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100012950","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100008990","name":"Universit\u00c3\u00a9 de Lorraine","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100008990","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004794","name":"Centre National de la Recherche Scientifique","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100004794","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"

\n We propose a probabilistic variant of Brill-Noether\u2019s algorithm for computing a basis of the Riemann-Roch space\n \n \n \n \n L<\/mml:mi>\n (<\/mml:mo>\n D<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n L(D)<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n associated to a divisor\n \n \n \n D<\/mml:mi>\n D<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n on a projective nodal plane curve\n \n \n \n \n C<\/mml:mi>\n <\/mml:mrow>\n \\mathbb {C}<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n over a sufficiently large perfect field\n \n \n \n k<\/mml:mi>\n k<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n . Our main result shows that this algorithm requires at most\n \n \n \n \n O<\/mml:mi>\n (<\/mml:mo>\n max<\/mml:mo>\n (<\/mml:mo>\n deg<\/mml:mi>\n \n \u2061\n \n <\/mml:mo>\n (<\/mml:mo>\n \n C<\/mml:mi>\n <\/mml:mrow>\n \n )<\/mml:mo>\n \n 2<\/mml:mn>\n \n \u03c9\n \n <\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n ,<\/mml:mo>\n deg<\/mml:mi>\n \n \u2061\n \n <\/mml:mo>\n (<\/mml:mo>\n \n D<\/mml:mi>\n +<\/mml:mo>\n <\/mml:msub>\n \n )<\/mml:mo>\n \n \u03c9\n \n <\/mml:mi>\n <\/mml:msup>\n )<\/mml:mo>\n )<\/mml:mo>\n <\/mml:mrow>\n O(\\max (\\deg (\\mathbb {C})^{2\\omega }, \\deg (D_+)^\\omega ))<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n arithmetic operations in\n \n \n \n k<\/mml:mi>\n k<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n , where\n \n \n \n \n \u03c9\n \n <\/mml:mi>\n \\omega<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n is a feasible exponent for matrix multiplication and\n \n \n \n \n D<\/mml:mi>\n +<\/mml:mo>\n <\/mml:msub>\n D_+<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n is the smallest effective divisor such that\n \n \n \n \n \n D<\/mml:mi>\n +<\/mml:mo>\n <\/mml:msub>\n \n \u2265\n \n <\/mml:mo>\n D<\/mml:mi>\n <\/mml:mrow>\n D_+\\geq D<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n . This improves the best known upper bounds on the complexity of computing Riemann-Roch spaces. Our algorithm may fail, but we show that provided that a few mild assumptions are satisfied, the failure probability is bounded by\n \n \n \n \n O<\/mml:mi>\n (<\/mml:mo>\n max<\/mml:mo>\n (<\/mml:mo>\n deg<\/mml:mi>\n \n \u2061\n \n <\/mml:mo>\n (<\/mml:mo>\n \n C<\/mml:mi>\n <\/mml:mrow>\n \n )<\/mml:mo>\n 4<\/mml:mn>\n <\/mml:msup>\n ,<\/mml:mo>\n deg<\/mml:mi>\n \n \u2061\n \n <\/mml:mo>\n (<\/mml:mo>\n \n D<\/mml:mi>\n +<\/mml:mo>\n <\/mml:msub>\n \n )<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:msup>\n )<\/mml:mo>\n \n \/<\/mml:mo>\n <\/mml:mrow>\n \n |\n \n <\/mml:mo>\n \n E<\/mml:mi>\n <\/mml:mrow>\n \n |\n \n <\/mml:mo>\n )<\/mml:mo>\n <\/mml:mrow>\n O(\\max (\\deg (\\mathbb {C})^4, \\deg (D_+)^2)\/\\lvert \\mathcal E\\rvert )<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n , where\n \n \n \n \n E<\/mml:mi>\n <\/mml:mrow>\n \\mathcal E<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n is a finite subset of\n \n \n \n k<\/mml:mi>\n k<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n in which we pick elements uniformly at random. We provide a freely available C++\/NTL implementation of the proposed algorithm and we present experimental data. In particular, our implementation enjoys a speedup larger than 6 on many examples (and larger than 200 on some instances over large finite fields) compared to the reference implementation in the Magma computer algebra system. As a by-product, our algorithm also yields a method for computing the group law on the Jacobian of a smooth plane curve of genus\n \n \n \n g<\/mml:mi>\n g<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n within\n \n \n \n \n O<\/mml:mi>\n (<\/mml:mo>\n \n g<\/mml:mi>\n \n \u03c9\n \n <\/mml:mi>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n O(g^\\omega )<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n operations in\n \n \n \n k<\/mml:mi>\n k<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n , which equals the best known complexity for this problem.\n <\/p>","DOI":"10.1090\/mcom\/3517","type":"journal-article","created":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T09:18:46Z","timestamp":1578475126000},"page":"2399-2433","source":"Crossref","is-referenced-by-count":9,"title":["A fast randomized geometric algorithm for computing Riemann-Roch spaces"],"prefix":"10.1090","volume":"89","author":[{"given":"Aude","family":"Le Gluher","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pierre-Jean","family":"Spaenlehauer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"14","published-online":{"date-parts":[[2020,2,18]]},"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-3-540-69392-5","volume-title":"Geometry of algebraic curves. Volume II","volume":"268","author":"Arbarello, Enrico","year":"2011","ISBN":"https:\/\/id.crossref.org\/isbn\/9783540426882"},{"key":"2","volume-title":"Introduction to commutative algebra","author":"Atiyah, M. F.","year":"1969"},{"key":"3","unstructured":"L. Babai, Monte-Carlo algorithms in graph isomorphism testing, Universit\u00e9 de Montr\u00e9al Technical Report, DMS (1979), no. 79-10."},{"issue":"3-4","key":"4","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1006\/jsco.1996.0125","article-title":"The Magma algebra system. I. The user language","volume":"24","author":"Bosma, Wieb","year":"1997","journal-title":"J. Symbolic Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"key":"5","doi-asserted-by":"publisher","first-page":"231","DOI":"10.2307\/2005828","article-title":"Triangular factorization and inversion by fast matrix multiplication","volume":"28","author":"Bunch, James R.","year":"1974","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"6","doi-asserted-by":"crossref","unstructured":"J. Canny, Some algebraic and geometric computations in PSPACE, Proc. of the twentieth annual ACM Symposium on Theory of Computing (STOC), ACM, 1988, pp. 460\u2013467.","DOI":"10.1145\/62212.62257"},{"issue":"7","key":"7","doi-asserted-by":"publisher","first-page":"693","DOI":"10.1007\/BF01178683","article-title":"On fast multiplication of polynomials over arbitrary algebras","volume":"28","author":"Cantor, David G.","year":"1991","journal-title":"Acta Inform.","ISSN":"https:\/\/id.crossref.org\/issn\/0001-5903","issn-type":"print"},{"issue":"3","key":"8","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1016\/S0747-7171(02)00135-9","article-title":"An elementary approach to subresultants theory","volume":"35","author":"El Kahoui, M\u2019hammed","year":"2003","journal-title":"J. Symbolic Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"key":"9","series-title":"Mathematics Lecture Note Series","volume-title":"Algebraic curves. An introduction to algebraic geometry","author":"Fulton, William","year":"1969"},{"issue":"1","key":"10","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1006\/jcom.2000.0571","article-title":"A Gr\u00f6bner free alternative for polynomial system solving","volume":"17","author":"Giusti, Marc","year":"2001","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"issue":"4","key":"11","first-page":"762","article-title":"Algebraic-geometric codes","volume":"46","author":"Goppa, V. D.","year":"1982","journal-title":"Izv. Akad. Nauk SSSR Ser. Mat.","ISSN":"https:\/\/id.crossref.org\/issn\/0373-2436","issn-type":"print"},{"key":"12","isbn-type":"print","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1007\/3-540-60114-7_19","article-title":"Computation in algebraic function fields for effective construction of algebraic-geometric codes","author":"Hach\u00e9, Ga\u00e9tan","year":"1995","ISBN":"https:\/\/id.crossref.org\/isbn\/3540601147"},{"issue":"6","key":"13","doi-asserted-by":"publisher","first-page":"1615","DOI":"10.1109\/18.476233","article-title":"Effective construction of algebraic geometry codes","volume":"41","author":"Hach\u00e9, Ga\u00e9tan","year":"1995","journal-title":"IEEE Trans. Inform. Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0018-9448","issn-type":"print"},{"issue":"4","key":"14","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":"15","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":"2","key":"16","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/0001-8708(91)90031-2","article-title":"Le formalisme du r\u00e9sultant","volume":"90","author":"Jouanolou, J.-P.","year":"1991","journal-title":"Adv. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0001-8708","issn-type":"print"},{"issue":"260","key":"17","doi-asserted-by":"publisher","first-page":"2213","DOI":"10.1090\/S0025-5718-07-01989-8","article-title":"Asymptotically fast group operations on Jacobians of general curves","volume":"76","author":"Khuri-Makdisi, Kamal","year":"2007","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"2","key":"18","doi-asserted-by":"crossref","first-page":"231","DOI":"10.24033\/bsmf.2096","article-title":"Algorithme de Brill-Noether et codes de Goppa","volume":"116","author":"Le Brigand, D.","year":"1988","journal-title":"Bull. Soc. Math. France","ISSN":"https:\/\/id.crossref.org\/issn\/0037-9484","issn-type":"print"},{"key":"19","isbn-type":"print","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1145\/2608628.2608664","article-title":"Powers of tensors and fast matrix multiplication","author":"Le Gall, Fran\u00e7ois","year":"2014","ISBN":"https:\/\/id.crossref.org\/isbn\/9781450325011"},{"key":"20","isbn-type":"print","first-page":"349","article-title":"Fast computation of the roots of polynomials over the ring of power series","author":"Neiger, Vincent","year":"2017","ISBN":"https:\/\/id.crossref.org\/isbn\/9781450350648"},{"key":"21","isbn-type":"print","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1145\/1277548.1277590","article-title":"Faster algorithms for the characteristic polynomial","author":"Pernet, Cl\u00e9ment","year":"2007","ISBN":"https:\/\/id.crossref.org\/isbn\/9781595937438"},{"key":"22","isbn-type":"print","first-page":"200","article-title":"Probabilistic algorithms for verification of polynomial identities","author":"Schwartz, Jacob T.","year":"1979","ISBN":"https:\/\/id.crossref.org\/isbn\/3540095195"},{"key":"23","series-title":"Bibliotheca Mathematica Teubneriana, Band 32","volume-title":"Vorlesungen \\\"{u}ber algebraische Geometrie: Geometrie auf einer Kurve, Riemannsche Fl\\\"{a}chen, Abelsche Integrale","author":"Severi, Francesco","year":"1968"},{"key":"24","unstructured":"A. Storjohann, Algorithms for matrix canonical forms, Ph.D. thesis, ETH Zurich, 2000."},{"key":"25","unstructured":"J. V. Der Hoeven and G. Lecerf, Fast computation of generic bivariate resultants, Preprint, 2019."},{"key":"26","isbn-type":"print","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1145\/3208976.3209020","article-title":"On computing the resultant of generic bivariate polynomials","author":"Villard, Gilles","year":"2018","ISBN":"https:\/\/id.crossref.org\/isbn\/9781450355506"},{"key":"27","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"},{"key":"28","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139856065","volume-title":"Modern computer algebra","author":"von zur Gathen, Joachim","year":"2013","ISBN":"https:\/\/id.crossref.org\/isbn\/9781107039032","edition":"3"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.ams.org\/mcom\/2020-89-325\/S0025-5718-2020-03517-0\/mcom3517_AM.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"http:\/\/www.ams.org\/mcom\/0000-000-00\/S0025-5718-2020-03517-0\/S0025-5718-2020-03517-0.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2020-89-325\/S0025-5718-2020-03517-0\/S0025-5718-2020-03517-0.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T03:47:08Z","timestamp":1776829628000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2020-89-325\/S0025-5718-2020-03517-0\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,18]]},"references-count":28,"journal-issue":{"issue":"325","published-print":{"date-parts":[[2020,9]]}},"alternative-id":["S0025-5718-2020-03517-0"],"URL":"https:\/\/doi.org\/10.1090\/mcom\/3517","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":[[2020,2,18]]}}}