Computing Boolean Border Bases
Jan Horáček, Martin Kreuzer, Ange-Salomé Messeng Ekossono · 2016
Given a 0-dimensional polynomial system in a polynomial ring over F_2 having only F_2-rational solutions, we optimize the Border Basis Algorithm (BBA) for solving this system by introducing a Boolean BBA. This algorithm is further improved by optimizing the linear algebra steps. We discuss ways to combine it with SAT solvers, optimized methods for performing the combinatorial steps involved in the algorithm, and various approaches to implement the linear algebra steps. Based on our C++ implementation, we provide some timings to compare sparse and dense representations of the coefficient matrices and to Gröebner basis methods.