×

A signature based border basis algorithm. (English) Zbl 1474.13056

Summary: The Border Basis Algorithm (BBA) still suffers from the lack of analogues of Buchberger’s criteria for avoiding unnecessary reductions. In this paper we develop a signature based technique which provides a first remedial step: signature bounds allow us to recognize multiple reductions of the same ancestor polynomial. The new signature based algorithm is then combined with the Boolean BBA for ideals of Boolean polynomials. Experiments show that it is at least 5 times faster than the standard Boolean BBA.

MSC:

13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
06E99 Boolean algebras (Boolean rings)
13P15 Solving polynomial systems; resultants
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Buchberger, B., Bruno Buchberger’s Ph.D. thesis 1965: an algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal, J. Symb. Comput., 41, 475-511 (2006) · Zbl 1158.01307 · doi:10.1016/j.jsc.2005.09.007
[2] Faugère, J.-C.: A new efficient algorithm for computing Gröbner bases without reduction to zero (F5). In: Proc. Conf. ISSAC 2002, pp. 75-83. ACM Press, New York (2002) · Zbl 1072.68664
[3] Eder, C.; Faugère, J-C, A survey on signature-based algorithms for computing Gröbner bases, J. Symb. Comput., 80, 719-784 (2017) · Zbl 1412.68306 · doi:10.1016/j.jsc.2016.07.031
[4] Mourrain, B.: A new criterion for normal form algorithms. In: Fossorier, M., Imai, H., Lin, S., Poli, A. (eds.) Proc. Conf. AAECC-13, Honolulu 1999, LNCS, Vol. 1719, pp. 440-443. Springer, Heidelberg (1999) · Zbl 0976.12005
[5] Kehrein, A.; Kreuzer, M., Computing border bases, J. Pure Appl. Alg., 205, 279-295 (2006) · Zbl 1097.13036 · doi:10.1016/j.jpaa.2005.07.006
[6] Horacek, J., Kreuzer, M., Messeng Ekossono, A.-S.: Computing Boolean border bases. In: Proc. Conf. SYNASC’16, Timisoara 2016. IEEE. www.sc-square.org/CSA/workshop1-papers/paper3.pdf
[7] Mourrain, B., Trébuchet, P.: Generalized normal forms and polynomial system solving. In: Proc. Conf. ISSAC’05, Beijing 2005, pp. 253-260. ACM Press, New York (2005) · Zbl 1360.68947
[8] Kaspar, S., Computing border bases without using a term ordering, Beitr. Algebra Geom., 54, 211-223 (2013) · Zbl 1266.13019 · doi:10.1007/s13366-011-0070-6
[9] The ApCoCoA Team, ApCoCoA: Applied Computations in Computer Algebra. http://apcocoa.uni-passau.de
[10] Kreuzer, M.; Robbiano, L., Computational Commutative Algebra 1 (2000), Heidelberg: Springer, Heidelberg · Zbl 0956.13008
[11] Kreuzer, M.; Robbiano, L., Computational Commutative Algebra 2 (2005), Heidelberg: Springer, Heidelberg · Zbl 1090.13021
[12] Gay, M., Burchard, J., Horacek, J., Messeng Ekossono, A.-S., Schubert, T., Becker, B., Kreuzer, M., Polian, I.: Small scale AES toolbox: algebraic and propositional formulas, circuit-implementations and fault equations. In: Proc. Conf. Trustworthy Manufacturing and Utilization of Secure Devices (TRUDEVICE 2016), Barcelona, 2016. http://upcommons.upc.edu/handle/2117/99210
[13] SageMath, the Sage Mathematics Software System (Version 7.5.1), The Sage Developers (2017). http://www.sagemath.org
[14] Brickenstein, M.; Dreyer, A., PolyBoRi: a framework for Gröbner basis computations with Boolean polynomials, J. Symb. Comput., 44, 1326-1345 (2009) · Zbl 1186.68571 · doi:10.1016/j.jsc.2008.02.017
[15] Soos, M.: The CryptoMiniSat 5 set of solvers at SAT Competition 2016. In: Baljo, T., Heule, M.J.H., Järvisalo, M. (eds.) Proc. SAT COMPETITION 2016, p. 28. University of Helsinki, Helsinki (2016)
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.