{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T13:19:02Z","timestamp":1776863942844,"version":"3.51.2"},"reference-count":28,"publisher":"American Mathematical Society (AMS)","issue":"297","license":[{"start":{"date-parts":[[2016,5,20]],"date-time":"2016-05-20T00:00:00Z","timestamp":1463702400000},"content-version":"am","delay-in-days":366,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-1005369"],"award-info":[{"award-number":["DMS-1005369"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"<p>This paper presents a new framework for computing Gr\u00f6bner bases for ideals and syzygy modules. It is proposed to work in a module that accommodates any given ideal and the corresponding syzygy module (for the given generators of the ideal). A strong Gr\u00f6bner basis for this module contains Gr\u00f6bner bases for both the ideal and the syzygy module. The main result is a simple characterization of strong Gr\u00f6bner bases. This characterization can detect useless S-polynomials without reductions, thus yields an efficient algorithm. It also explains all the rewritten rules used in F5 and the recent papers in the literature. Rigorous proofs are given for the correctness and finite termination of the algorithm. For any term order for an ideal, one may vary signature orders (i.e. the term orders for the syzygy module). It is shown by computer experiments on benchmark examples that signature orders based on weighted terms are much better than other signature orders. This is useful for practical computation. Also, since computing G\u00f6bner bases for syzygies is a main computational task for free resolutions in commutative algebra, the algorithm of this paper should be useful for computing free resolutions in practice.<\/p>","DOI":"10.1090\/mcom\/2969","type":"journal-article","created":{"date-parts":[[2015,5,20]],"date-time":"2015-05-20T13:29:39Z","timestamp":1432128579000},"page":"449-465","source":"Crossref","is-referenced-by-count":40,"title":["A new framework for computing Gr\u00f6bner bases"],"prefix":"10.1090","volume":"85","author":[{"given":"Shuhong","family":"Gao","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"suffix":"IV","given":"Frank","family":"Volny","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mingsheng","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"14","published-online":{"date-parts":[[2015,5,20]]},"reference":[{"issue":"9","key":"1","doi-asserted-by":"publisher","first-page":"1017","DOI":"10.1016\/j.jsc.2011.05.004","article-title":"The F5 criterion revised","volume":"46","author":"Arri, Alberto","year":"2011","journal-title":"J. Symbolic Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"key":"2","unstructured":"B. Buchberger, Ein algorithmus zum auffinden der basiselemente des restklassenringes nach einem nulldimensionalen polynomideal, Ph.D. thesis, Leopold-Franzens University, 1965."},{"key":"3","doi-asserted-by":"crossref","unstructured":"B. Buchberger, Gr\u00f6bner-bases: An Algorithmic Method in Polynomial Ideal Theory., Reidel Publishing Company, Dodrecht - Boston - Lancaster, 1985 (English).","DOI":"10.1007\/978-94-009-5225-6_6"},{"key":"4","isbn-type":"print","first-page":"3","article-title":"A criterion for detecting unnecessary reductions in the construction of Gr\u00f6bner-bases","author":"Buchberger, B.","year":"1979","ISBN":"https:\/\/id.crossref.org\/isbn\/3540095195"},{"key":"5","series-title":"Lecture Notes in Computer Science","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-88403-3","volume-title":"Post-quantum cryptography","volume":"5299","year":"2008","ISBN":"https:\/\/id.crossref.org\/isbn\/9783540884026"},{"key":"6","isbn-type":"print","doi-asserted-by":"publisher","first-page":"392","DOI":"10.1007\/3-540-45539-6_27","article-title":"Efficient algorithms for solving overdefined systems of multivariate polynomial equations","author":"Courtois, Nicolas","year":"2000","ISBN":"https:\/\/id.crossref.org\/isbn\/3540675175"},{"key":"7","isbn-type":"print","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1145\/1993886.1993906","article-title":"Signature-based algorithms to compute Gr\u00f6bner bases","author":"Eder, Christian","year":"2011","ISBN":"https:\/\/id.crossref.org\/isbn\/9781450306751"},{"issue":"12","key":"8","doi-asserted-by":"publisher","first-page":"1442","DOI":"10.1016\/j.jsc.2010.06.019","article-title":"F5C: a variant of Faug\u00e8re\u2019s F5 algorithm with reduced Gr\u00f6bner bases","volume":"45","author":"Eder, Christian","year":"2010","journal-title":"J. Symbolic Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"key":"9","doi-asserted-by":"crossref","unstructured":"C. Eder and B.H. Roune, Signature rewriting in gr\u00f6bner basis computation, ISSAC 2013: Proceedings of the 2013 international symposium of symbolic and algebraic computation (2013), 331\u2013228.","DOI":"10.1145\/2465506.2465522"},{"issue":"1-3","key":"10","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/S0022-4049(99)00005-5","article-title":"A new efficient algorithm for computing Gr\u00f6bner bases (\ud835\udc39\u2084)","volume":"139","author":"Faug\u00e9re, Jean-Charles","year":"1999","journal-title":"J. Pure Appl. Algebra","ISSN":"https:\/\/id.crossref.org\/issn\/0022-4049","issn-type":"print"},{"key":"11","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1145\/780506.780516","article-title":"A new efficient algorithm for computing Gr\u00f6bner bases without reduction to zero (\ud835\udc39\u2085)","author":"Faug\u00e8re, Jean-Charles","year":"2002"},{"key":"12","isbn-type":"print","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1007\/978-3-540-45146-4_3","article-title":"Algebraic cryptanalysis of hidden field equation (HFE) cryptosystems using Gr\u00f6bner bases","author":"Faug\u00e8re, Jean-Charles","year":"2003","ISBN":"https:\/\/id.crossref.org\/isbn\/3540406743"},{"key":"13","isbn-type":"print","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1145\/1837934.1837944","article-title":"A new incremental algorithm for computing Groebner bases","author":"Gao, Shuhong","year":"2010","ISBN":"https:\/\/id.crossref.org\/isbn\/9781450301503"},{"key":"14","unstructured":"J. Gash, On efficient computation of Gr\u00f6bner bases, Ph.D. dissertation, Indiana University, Bloomington, IN (2008)."},{"issue":"12","key":"15","doi-asserted-by":"publisher","first-page":"1330","DOI":"10.1016\/j.jsc.2010.06.013","article-title":"Extended \ud835\udc39\u2085 criteria","volume":"45","author":"Hashemi, Amir","year":"2010","journal-title":"J. Symbolic Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"key":"16","unstructured":"L. Huang, A new conception for computing Gr\u00f6bner basis and its applications, CoRR arXiv:1012.5425v2 (2010)."},{"key":"17","doi-asserted-by":"crossref","unstructured":"D. Lazard, Gr\u00f6bner-bases, Gaussian elimination and resolution of systems of algebraic equations, EUROCAL \u201983: Proceedings of the European Computer Algebra Conference on Computer Algebra (London, UK), Springer-Verlag, 1983, pp. 146\u2013156.","DOI":"10.1007\/3-540-12868-9_99"},{"issue":"2","key":"18","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1007\/BF01386834","article-title":"Gr\u00f6bner bases of ideals defined by functionals with an application to ideals of projective points","volume":"4","author":"Marinari, M. G.","year":"1993","journal-title":"Appl. Algebra Engrg. Comm. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0938-1279","issn-type":"print"},{"key":"19","doi-asserted-by":"crossref","unstructured":"H. M. M\u00f6ller, T. Mora, and C. Traverso, Gr\u00f6bner bases computation using syzygies, ISSAC \u201992: Papers from the international symposium on Symbolic and algebraic computation (New York, NY, USA), ACM, 1992, pp. 320\u2013328.","DOI":"10.1145\/143242.143343"},{"key":"20","doi-asserted-by":"crossref","unstructured":"S. Pan, Y. Hu, and B. Wang, The termination of the f5 algorithm revisited, ISSAC 2013: Proceedings of the 2013 International Symposium of Symbolic and Algebraic Computation (2013), 291\u2013298.","DOI":"10.1145\/2465506.2465520"},{"key":"21","isbn-type":"print","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1007\/3-540-68697-5_4","article-title":"Asymmetric cryptography with a hidden monomial and a candidate algorithm for \u224364 bits asymmetric signatures","author":"Patarin, Jacques","year":"1996","ISBN":"https:\/\/id.crossref.org\/isbn\/3540615121"},{"key":"22","doi-asserted-by":"crossref","unstructured":"B. H. Roune and M. Stillman, Practical Gr\u00f6bner Basis Computation, ISSAC\u201912: Proceedings of the 2012 International Symposium on Symbolic and Algebraic Computation (Grenoble, France), ACM, 2012.","DOI":"10.1145\/2442829.2442860"},{"key":"23","unstructured":"T. Stegers, Faug\u00e8re\u2019s F5 algorithm revisited, Cryptology ePrint Archive Report 2006\/404 (2006)."},{"key":"24","doi-asserted-by":"crossref","unstructured":"Y. Sun, D. K. Wang, D. X. Ma, and Y. Zhang, A signature-based algorithm for computing Gr\u00f6bner bases in solvable polynomial algebras, ISSAC\u201912: Proceedings of the 2012 International Symposium on Symbolic and Algebraic Computation (Grenoble, France), ACM, 2012, pp. 351\u2013358.","DOI":"10.1145\/2442829.2442879"},{"key":"25","unstructured":"Y. Sun and D.K. Wang, Extending the gvw algorithm to compute gr\u00f6bner bases, Submitted to Sci. China Math. (2013)."},{"key":"26","unstructured":"Y. Sun, Signature-based gr\u00f6bner basis algorithms extended MMM algorithm for computing Gr\u00f6bner bases, CoRR arXiv:1308.2371 (2013)."},{"key":"27","isbn-type":"print","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1145\/1993886.1993936","article-title":"A generalized criterion for signature related Gr\u00f6bner basis algorithms","author":"Sun, Yao","year":"2011","ISBN":"https:\/\/id.crossref.org\/isbn\/9781450306751"},{"key":"28","unstructured":"F. Volny IV, New algorithms for computing Gr\u00f6bner bases, PhD thesis, Clemson University (2011)."}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2016-85-297\/S0025-5718-2015-02969-X\/S0025-5718-2015-02969-X.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2016-85-297\/S0025-5718-2015-02969-X\/S0025-5718-2015-02969-X.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T18:38:32Z","timestamp":1776796712000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2016-85-297\/S0025-5718-2015-02969-X\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,5,20]]},"references-count":28,"journal-issue":{"issue":"297","published-print":{"date-parts":[[2016,1]]}},"alternative-id":["S0025-5718-2015-02969-X"],"URL":"https:\/\/doi.org\/10.1090\/mcom\/2969","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":[[2015,5,20]]}}}