Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

Request Permissions   Purchase Content 
 

 

A new framework for computing Gröbner bases


Authors: Shuhong Gao, Frank Volny IV and Mingsheng Wang
Journal: Math. Comp. 85 (2016), 449-465
MSC (2010): Primary 13P10, 68W10
DOI: https://doi.org/10.1090/mcom/2969
Published electronically: May 20, 2015
MathSciNet review: 3404457
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: This paper presents a new framework for computing Gröbner 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öbner basis for this module contains Gröbner bases for both the ideal and the syzygy module. The main result is a simple characterization of strong Gröbner 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öbner 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.


References [Enhancements On Off] (What's this?)

  • [1] Alberto Arri and John Perry, The F5 criterion revised, J. Symbolic Comput. 46 (2011), no. 9, 1017–1029. MR 2819324, https://doi.org/10.1016/j.jsc.2011.05.004
  • [2] B. Buchberger, Ein algorithmus zum auffinden der basiselemente des restklassenringes nach einem nulldimensionalen polynomideal, Ph.D. thesis, Leopold-Franzens University, 1965.
  • [3] B. Buchberger, Gröbner-bases: An Algorithmic Method in Polynomial Ideal Theory., Reidel Publishing Company, Dodrecht - Boston - Lancaster, 1985 (English).
  • [4] B. Buchberger, A criterion for detecting unnecessary reductions in the construction of Gröbner-bases, Symbolic and algebraic computation (EUROSAM ’79, Internat. Sympos., Marseille, 1979) Lecture Notes in Comput. Sci., vol. 72, Springer, Berlin-New York, 1979, pp. 3–21. MR 575678
  • [5] Johannes Buchmann and Jintai Ding (eds.), Post-quantum cryptography, Lecture Notes in Computer Science, vol. 5299, Springer, Berlin, 2008. MR 2789106
  • [6] Nicolas Courtois, Alexander Klimov, Jacques Patarin, and Adi Shamir, Efficient algorithms for solving overdefined systems of multivariate polynomial equations, Advances in cryptology—EUROCRYPT 2000 (Bruges), Lecture Notes in Comput. Sci., vol. 1807, Springer, Berlin, 2000, pp. 392–407. MR 1772028, https://doi.org/10.1007/3-540-45539-6_27
  • [7] Christian Eder and John Perry, Signature-based algorithms to compute Gröbner bases, ISSAC 2011—Proceedings of the 36th International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2011, pp. 99–106. MR 2895200, https://doi.org/10.1145/1993886.1993906
  • [8] Christian Eder and John Perry, F5C: a variant of Faugère’s F5 algorithm with reduced Gröbner bases, J. Symbolic Comput. 45 (2010), no. 12, 1442–1458. MR 2733388, https://doi.org/10.1016/j.jsc.2010.06.019
  • [9] C. Eder and B.H. Roune, Signature rewriting in gröbner basis computation, ISSAC 2013: Proceedings of the 2013 international symposium of symbolic and algebraic computation (2013), 331-228.
  • [10] Jean-Charles Faugére, A new efficient algorithm for computing Gröbner bases (𝐹₄), J. Pure Appl. Algebra 139 (1999), no. 1-3, 61–88. Effective methods in algebraic geometry (Saint-Malo, 1998). MR 1700538, https://doi.org/10.1016/S0022-4049(99)00005-5
  • [11] Jean-Charles Faugère, A new efficient algorithm for computing Gröbner bases without reduction to zero (𝐹₅), Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2002, pp. 75–83. MR 2035234, https://doi.org/10.1145/780506.780516
  • [12] Jean-Charles Faugère and Antoine Joux, Algebraic cryptanalysis of hidden field equation (HFE) cryptosystems using Gröbner bases, Advances in cryptology—CRYPTO 2003, Lecture Notes in Comput. Sci., vol. 2729, Springer, Berlin, 2003, pp. 44–60. MR 2093185, https://doi.org/10.1007/978-3-540-45146-4_3
  • [13] Shuhong Gao, Yinhua Guan, and Frank Volny IV, A new incremental algorithm for computing Groebner bases, ISSAC 2010—Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2010, pp. 13–19. MR 2920531, https://doi.org/10.1145/1837934.1837944
  • [14] J. Gash, On efficient computation of Gröbner bases, Ph.D. dissertation, Indiana University, Bloomington, IN (2008).
  • [15] Amir Hashemi and Gwénolé Ars, Extended 𝐹₅ criteria, J. Symbolic Comput. 45 (2010), no. 12, 1330–1340. MR 2733382, https://doi.org/10.1016/j.jsc.2010.06.013
  • [16] L. Huang, A new conception for computing Gröbner basis and its applications, CoRR arXiv:1012.5425v2 (2010).
  • [17] D. Lazard, Gröbner-bases, Gaussian elimination and resolution of systems of algebraic equations, EUROCAL '83: Proceedings of the European Computer Algebra Conference on Computer Algebra (London, UK), Springer-Verlag, 1983, pp. 146-156.
  • [18] M. G. Marinari, H. M. Möller, and T. Mora, Gröbner bases of ideals defined by functionals with an application to ideals of projective points, Appl. Algebra Engrg. Comm. Comput. 4 (1993), no. 2, 103–145. MR 1223853, https://doi.org/10.1007/BF01386834
  • [19] H. M. Möller, T. Mora, and C. Traverso, Gröbner bases computation using syzygies, ISSAC '92: Papers from the international symposium on Symbolic and algebraic computation (New York, NY, USA), ACM, 1992, pp. 320-328.
  • [20] 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-298.
  • [21] Jacques Patarin, Asymmetric cryptography with a hidden monomial and a candidate algorithm for ≃64 bits asymmetric signatures, Advances in cryptology—CRYPTO ’96 (Santa Barbara, CA), Lecture Notes in Comput. Sci., vol. 1109, Springer, Berlin, 1996, pp. 45–60. MR 1480670, https://doi.org/10.1007/3-540-68697-5_4
  • [22] B. H. Roune and M. Stillman, Practical Gröbner Basis Computation, ISSAC'12: Proceedings of the 2012 International Symposium on Symbolic and Algebraic Computation (Grenoble, France), ACM, 2012.
  • [23] T. Stegers, Faugère's F5 algorithm revisited, Cryptology ePrint Archive Report 2006/404 (2006).
  • [24] Y. Sun, D. K. Wang, D. X. Ma, and Y. Zhang, A signature-based algorithm for computing Gröbner bases in solvable polynomial algebras, ISSAC'12: Proceedings of the 2012 International Symposium on Symbolic and Algebraic Computation (Grenoble, France), ACM, 2012, pp. 351-358.
  • [25] Y. Sun and D.K. Wang, Extending the gvw algorithm to compute gröbner bases, Submitted to Sci. China Math. (2013).
  • [26] Y. Sun, Signature-based gröbner basis algorithms extended MMM algorithm for computing Gröbner bases, CoRR arXiv:1308.2371 (2013).
  • [27] Yao Sun and Dingkang Wang, A generalized criterion for signature related Gröbner basis algorithms, ISSAC 2011—Proceedings of the 36th International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2011, pp. 337–344. MR 2895230, https://doi.org/10.1145/1993886.1993936
  • [28] F. Volny IV, New algorithms for computing Gröbner bases, PhD thesis, Clemson University (2011).

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 13P10, 68W10

Retrieve articles in all journals with MSC (2010): 13P10, 68W10


Additional Information

Shuhong Gao
Affiliation: Department of Mathematical Sciences, Clemson University, Clemson, South Carolina 29634-0975
Email: sgao@clemson.edu

Frank Volny IV
Affiliation: Department of Mathematical Sciences, Clemson University, Clemson, South Carolina 29634-0975
Email: fvolny4@gmail.com

Mingsheng Wang
Affiliation: Information Security Lab, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100190, People’s Republic of China
Email: mingsheng_wang@aliyun.com

DOI: https://doi.org/10.1090/mcom/2969
Keywords: Gr\"obner basis, Buchberger's algorithm, Syzygy module, F5 algorithm, module
Received by editor(s): July 25, 2013
Received by editor(s) in revised form: May 9, 2014
Published electronically: May 20, 2015
Additional Notes: The work presented in this paper was partially supported by the 973 Project (No. 2013CB834203), the National Science Foundation of China under Grant 11171323, and the National Science Foundation of USA under grants DMS-1005369 and CCF-0830481
Article copyright: © Copyright 2015 American Mathematical Society