Divide and Conquer Algorithm for Gröbner Basis over Binary Field

Abstract

In this paper we present an algorithm for nding Gröbner basis in binary multivariate polynomial ring F2 [x1; x2; :::; xn] and for which the main goal is to solve binary multivariate nonlinear system; instead of the existing methods mostly based on linearization. The main idea of our method is well known divide and conquer recurrence; that in this case the Buchberger algorithm is applied only at the end of the combining phase. For data representation, every single polynomial in the ring can be consid- ered to be a boolean object, so in symbolic computation perspective that the polynomial can be represented as a member of power set of integers and these integers represent variable symbol of the polynomial. Thus, with this point of view, details of the algorithm can be stated in algebraic computation codes. At the end of the paper, we give a general complex- ity of the algorithm and also present some facts from the implementation aspect