ブール多項式環$mathbb{Z}_2(x_1,...,x_2)$におけるイデアル$<g>$のブーリアングレブナー基底の計算について

Abstract

Boolean Gröbner bases are studied mainly in connection with cryptanalysis and formal verifica— tion [2]. Every Boolean Gröbner basis can be constructed as a subset of the corresponding (non Boolean) Gröbner basis.Therefore many methods to compute Boolean Gröbner bases are based on the ones for usual Gröbner bases (e.g. Buchberger's algorithm). In this paper we propose an algorithm that compute a Boolean Gröbner basis for an ideal generated by a given Boolean polynomial over Z2 (x1, ... , xn ). Wei mplemented the algorithm with using binary decision diagram (and zerosuppressed one) for the data structure of Boolean polynomials. Numerical experiments in the article imply that the proposed method and its implementation is more efficient than traditional ones in some cases.