A new framework for computing Gröbner bases

Gao, Shuhong; Volny, Frank, IV; Wang, Mingsheng

doi:10.1090/mcom/2969

A new framework for computing Gröbner bases
HTML articles powered by AMS MathViewer

by Shuhong Gao, Frank Volny IV and Mingsheng Wang PDF

Math. Comp. 85 (2016), 449-465 Request permission

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

Alberto Arri and John Perry, The F5 criterion revised, J. Symbolic Comput. 46 (2011), no. 9, 1017–1029. MR 2819324, DOI 10.1016/j.jsc.2011.05.004
B. Buchberger, Ein algorithmus zum auffinden der basiselemente des restklassenringes nach einem nulldimensionalen polynomideal, Ph.D. thesis, Leopold-Franzens University, 1965.
B. Buchberger, Gröbner-bases: An Algorithmic Method in Polynomial Ideal Theory., Reidel Publishing Company, Dodrecht - Boston - Lancaster, 1985 (English).
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
Johannes Buchmann and Jintai Ding (eds.), Post-quantum cryptography, Lecture Notes in Computer Science, vol. 5299, Springer, Berlin, 2008. MR 2789106, DOI 10.1007/978-3-540-88403-3
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, DOI 10.1007/3-540-45539-6_{2}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, DOI 10.1145/1993886.1993906
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, DOI 10.1016/j.jsc.2010.06.019
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.
Jean-Charles Faugére, A new efficient algorithm for computing Gröbner bases $(F_4)$, J. Pure Appl. Algebra 139 (1999), no. 1-3, 61–88. Effective methods in algebraic geometry (Saint-Malo, 1998). MR 1700538, DOI 10.1016/S0022-4049(99)00005-5
Jean-Charles Faugère, A new efficient algorithm for computing Gröbner bases without reduction to zero $(F_5)$, Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2002, pp. 75–83. MR 2035234, DOI 10.1145/780506.780516
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, DOI 10.1007/978-3-540-45146-4_{3}
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, DOI 10.1145/1837934.1837944
J. Gash, On efficient computation of Gröbner bases, Ph.D. dissertation, Indiana University, Bloomington, IN (2008).
Amir Hashemi and Gwénolé Ars, Extended $\rm F_5$ criteria, J. Symbolic Comput. 45 (2010), no. 12, 1330–1340. MR 2733382, DOI 10.1016/j.jsc.2010.06.013
L. Huang, A new conception for computing Gröbner basis and its applications, CoRR arXiv:1012.5425v2 (2010).
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.
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, DOI 10.1007/BF01386834
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.
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.
Jacques Patarin, Asymmetric cryptography with a hidden monomial and a candidate algorithm for $\simeq 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, DOI 10.1007/3-540-68697-5_{4}
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.
T. Stegers, Faugère’s F5 algorithm revisited, Cryptology ePrint Archive Report 2006/404 (2006).
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.
Y. Sun and D.K. Wang, Extending the gvw algorithm to compute gröbner bases, Submitted to Sci. China Math. (2013).
Y. Sun, Signature-based gröbner basis algorithms extended MMM algorithm for computing Gröbner bases, CoRR arXiv:1308.2371 (2013).
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, DOI 10.1145/1993886.1993936
F. Volny IV, New algorithms for computing Gröbner bases, PhD thesis, Clemson University (2011).