28.9 Boolean Polynomials

Module: sage.rings.polynomial.pbori

Boolean Polynomials.

Elements of the quotient ring

$\displaystyle \mathbf{F}_2[x_1,...,x_n]/<x_1^2+x_1,...,x_n^2+x_n>.$

are called boolean polynomials. Boolean polynomials arise naturally in cryptography, coding theory, formal logic, chip design and other areas. This implementation is a thin wrapper around the POLYBORI library by Michael Brickenstein and Alexander Dreyer.

``Boolean polynomials can be modelled in a rather simple way, with both coefficients and degree per variable lying in $ \{0, 1\}$ . The ring of Boolean polynomials is, however, not a polynomial ring, but rather the quotient ring of the polynomial ring over the field with two elements modulo the field equations $ x^2=x$ for each variable $ x$ . Therefore, the usual polynomial data structures seem not to be appropriate for fast Groebner basis computations. We introduce a specialised data structure for Boolean polynomials based on zero-suppressed binary decision diagrams (ZDDs), which is capable of handling these polynomials more efficiently with respect to memory consumption and also computational speed. Furthermore, we concentrate on high-level algorithmic aspects, taking into account the new data structures as well as structural properties of Boolean polynomials.'' - [BD07]

Author Log:

Consider the ideal

$\displaystyle <ab + cd + 1, ace + de, abe + ce, bc + cde + 1>.$

First, we compute the lexicographical Groebner basis in the polynomial ring

$\displaystyle R = \mathbf{F}_2[a,b,c,d,e].$

sage: P.<a,b,c,d,e> = PolynomialRing(GF(2), 5, order='lex')
sage: I1 = ideal([a*b + c*d + 1, a*c*e + d*e, a*b*e + c*e, b*c + c*d*e + 1])
sage: for f in I1.groebner_basis():
...     f
d^4*e^2 + d^4*e + d^3*e + d^2*e^2 + d^2*e + d*e + e
c*e + d^3*e^2 + d^3*e + d^2*e^2 + d*e
b*e + d*e^2 + d*e + e
b*c + d^3*e^2 + d^3*e + d^2*e^2 + d*e + e + 1
a + c^2*d + c + d^2*e

If one wants to solve this system over the algebraic closure of $ \mathbf{F}_2$ then this Groebner basis was the one to consider. If one wants solutions over $ \mathbf{F}_2$ only then one adds the field polynomials to the ideal to force the solutions in $ \mathbf{F}_2$ .

sage: J = I1 + sage.rings.ideal.FieldIdeal(P)
sage: for f in J.groebner_basis():
...     f
e
d^2 + d
c + 1
b + 1
a + d + 1

So the solutions over $ \mathbf{F}_2$ are $ \{e=0, d=1, c=1, b=1, a=0\}$ and $ \{e=0,
d=0, c=1, b=1, a=1\}$ .

We can express the restriction to $ \mathbf{F}_2$ by considering the quotient ring. If $ I$ is an ideal in $ \mathbf{F}[x_1, ..., x_n]$ then the ideals in the quotient ring $ \mathbf{F}[x_1, ..., x_n]/I$ are in one-to-one correspondence with the ideals of $ \mathbf{F}[x_0, ..., x_n]$ containing $ I$ (that is, the ideals $ J$ satisfying $ I \subset J \subset P$ ).

sage: Q = P.quotient( sage.rings.ideal.FieldIdeal(P) )
sage: I2 = ideal([Q(f) for f in I1.gens()])
sage: for f in I2.groebner_basis():
...     f
ebar
cbar + 1
bbar + 1
abar + dbar + 1

This quotient ring is exactly what POLYBORI handles well.

sage: B.<a,b,c,d,e> = BooleanPolynomialRing(5, order='lex')
sage: I2 = ideal([B(f) for f in I1.gens()])
sage: for f in I2.groebner_basis():
...     f
a + d + 1
b + 1
c + 1
e

Note that $ d^2 + d$ is not representable in $ B == Q$ . Also note, that POLYBORI cannot play out its strength in such small examples, i.e. working in the polynomial ring might be faster for small examples like this.



Subsections
See About this document... for information on suggesting changes.