Involutive method for computing Gröbner bases over $$ \mathbb{F}_2 $$
Vladimir P. Gerdt, M. V. Zinin · Programming and Computer Software · 2008
In this paper, an involutive algorithm for computation of Gröbner bases for polynomial ideals in a ring of polynomials in many variables over the finite field $$ \mathbb{F}_2 $$ with the values of variables belonging of $$ \mathbb{F}_2 $$ is considered. The algorithm uses Janet division and is specialized for a graded reverse lexicographical order of monomials. We compare efficiency of this algorithm and its implementation in C++ with that of the Buchberger algorithm, as well as with the algorithms of computation of Gröbner bases that are built in the computer algebra systems Singular and CoCoA and in the FGb library for Maple. For the sake of comparison, we took widely used examples of computation of Gröbner bases over ℚ and adapted them for $$ \mathbb{F}_2 $$ . Polynomial systems over $$ \mathbb{F}_2 $$ with the values of variables in $$ \mathbb{F}_2 $$ are of interest, in particular, for modeling quantum computation and a number of cryptanalysis problems.