Module: sage.rings.polynomial.pbori
Boolean Polynomials.
Elements of the quotient ring
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
. 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
for each
variable
. 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
First, we compute the lexicographical Groebner basis in the polynomial ring
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
then this Groebner basis was the one to consider. If one wants
solutions over
only then one adds the field polynomials to the
ideal to force the solutions in
.
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
are
and
.
We can express the restriction to
by considering the quotient
ring. If
is an ideal in
then the ideals in the
quotient ring
are in one-to-one correspondence
with the ideals of
containing
(that is, the
ideals
satisfying
).
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
is not representable in
. 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.