BooleanGB -- Groebner Bases for Ideals in Boolean Polynomial Quotient Ring
Description
BooleanGB is a package to compute Groebner Bases in lexicographic order for polynomial ideals in the quotient ring F2[x1, ..., xn]/J, where J is the ideal generated by field polynomials xi2 - xi for i ∈{1, ..., n}. The algorithm is implemented bitwise rather than symbolically, which reduces the computational complexity.
i1 : n = 3;
i2 : R = ZZ/2[vars(0)..vars(n-1)];
i3 : J = apply( gens R, x -> x^2 + x);
i4 : QR = R/J;
i5 : I = ideal(a+b,b);
o5 : Ideal of QR
i6 : gbBoolean I
o6 = ideal (b, a)
o6 : Ideal of QR
i7 : gens gb I
o7 = | b a |
1 2
o7 : Matrix QR <--- QR
Caveat
BooleanGB always assumes that the ideal is in the Boolean quotient ring, i.e., F2[x1, ..., xn] / <x12-x1, ..., xn2-xn >, regardless of the ring in which the ideal was generated. Thus, any ideal in the base ring is promoted to the quotient ring automatically, even if the quotient ring has not been defined.