A pommaret division algorithm for computing Grobner bases in boolean rings

Abstract

In this paper an involutive algorithm for construction of Grobner bases in Boolean rings is presented. The algorithm exploits the Pommaret monomial division as an involutive division. In distinction to other approaches and due to special properties of Pommaret division the algorithm allows to perform the Grobner basis computation directly in a Boolean ring which can be defined as the quotient ring F2[x1,...,xn],<x12+x1,...,xn2+xn>. Some related cardinality bounds for Pommaret and Grobner bases are derived. Efficiency of our first implementation of the algorithm is illustrated by a number of serial benchmarks.