×

Termination of the F5 algorithm. (English. Russian original) Zbl 1323.68598

Program. Comput. Softw. 40, No. 2, 47-57 (2014); translation from Programmirovanie 40, No. 2 (2014).
Summary: The F5 algorithm, which calculates the Gröbner basis of an ideal generated by homogeneous polynomials, was proposed by J.-C. Faugère [in: Proceedings of the 2002 international symposium on symbolic and algebraic computation, ISSAC 2002. New York, NY: ACM Press. 75–83 (2002; Zbl 1072.68664)]; simultaneously, the correctness of this algorithm was proved under the condition of termination. However, termination itself was demonstrated only for a regular sequence of polynomials. In this paper, it is proved that the algorithm terminates for any input data. First, it is shown that if the algorithm does not terminate, it eventually generates two polynomials where the first is a reductor for the second. However, it is not argued that such a reduction is permitted by all the criteria introduced in F5. Next, it is shown that if such a pair exists, then there exists another pair for which the reduction is permitted by all the criteria, which is impossible.

MSC:

68W30 Symbolic computation and algebraic computation
13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)

Citations:

Zbl 1072.68664

Software:

F5C
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ars, G., Applications des bases de Gröbner à la cryptographie, Rennes: Universite — de Rennes 1, 2005.
[2] Baader, F. and Nipkow T., Term Rewriting and All That, Cambridge: Cambridge Univ. Press, 1998. · Zbl 0948.68098
[3] Eder, C, Improving incremental signature-based Groebner basis algorithms, ArXiv e-prints. 2012.-January.-1201.6472.
[4] Eder, C., Gash, J., and Perry, J., Modifying Faugère’s F5 algorithm to ensure termination, ACM Commun. Comput. Algebra, 2011, vol. 45, no. 1/2, pp. 70-89. · Zbl 1305.68353 · doi:10.1145/2016567.2016574
[5] Eder, C. and Perry, J., F5C: A variant of Faugère’s F5 algorithm with reduced Gröbner bases, J. Symb. Comput., 2010, vol. 45, no. 12, pp. 1442-1458. · Zbl 1227.13018 · doi:10.1016/j.jsc.2010.06.019
[6] Faugère, JC, A new efficient algorithm for computing Gröbner bases without reduction to zero (F5), 75-83 (2002), New York · Zbl 1072.68664 · doi:10.1145/780506.780516
[7] Gao, Sh; Guan, Y.; Volny, F., A new incremental algorithm for computing Gröbner bases, 13-19 (2010), New York · Zbl 1321.68531 · doi:10.1145/1837934.1837944
[8] Gao, Sh; Volny, F.; Wang, M., A new algorithm for computing Gröbner bases, 13-19 (2010), New York · Zbl 1321.68531 · doi:10.1145/1837934.1837944
[9] Gash, J.M., On efficient computation of Gröbner bases, Ph.D. Thesis, Indiana Univ., Indianapolis, 2008.
[10] Hashemi, A. and Ars, G., Extended F5 criteria, J. Symb. Comput., 2010, vol. 45, no. 12, pp. 1330-1340. · Zbl 1218.13014 · doi:10.1016/j.jsc.2010.06.013
[11] Huang, L., A new conception for computing Gröbner basis and its applications, ArXiv e-prints. XII 2010.
[12] Pan, S., Hu, Y., and Wang, B., The termination of algorithms for computing Gröbner bases, ArXiv e-prints. 2012. February. 1202.3524.
[13] Roune, B. and Stillman, M., Practical Gröbner basis computation, ArXiv e-prints. 2012. June. 1206.6940. · Zbl 1308.68185
[14] Stegers, T., Faugère’s F5 Algorithm revisited, IACR Cryptology ePrint Archive, 2006, vol. 404.
[15] Sun, Y. and Wang, D., A new proof for the correctness of F5 (F5-like) algorithm, ArXiv e-prints. 2010. April. 1004.0084.
[16] Sun, Y. and Wang, D., The F5 algorithm in Buchberger’s style, J. Syst. Sci. Complexity, 2012, vol. 24, pp. 1218-1231. · Zbl 1339.68322 · doi:10.1007/s11424-011-0218-3
[17] German, O.N., Proof of the Faugère criterion for the F5 algorithm, Mat. Zametki, 2010, vol. 88, no. 4, pp. 502-510. · Zbl 1258.13031 · doi:10.4213/mzm8849
[18] Zobnin, A.I., Generalization of the F5 algorithm for calculating Gröbner bases for polynomial ideals, Program. Comput. Software, 2010, vol. 36, no. 2, pp. 75-82. · Zbl 1204.13001 · doi:10.1134/S0361768810020040
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.