Module pbori

File: sage/rings/polynomial/pbori.pyx (starting at line 1)

Boolean Polynomials.

Elements of the quotient ring

    $$\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]

AUTHORS:
    -- Michael Brickenstein: \PolyBoRi author
    -- Alexander Dreyer: \PolyBoRi author
    -- Burcin Erocal <burcin@erocal.org>: main \SAGE wrapper author
    -- Martin Albrecht <malb@informatik.uni-bremen.de>: some contributions to the \SAGE wrapper

EXAMPLES:

Consider the ideal

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

First, we compute the lexicographical Groebner basis in the polynomial
ring $$R = \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 $\F_2$
then this Groebner basis was the one to consider. If one wants
solutions over $\F_2$ only then one adds the field polynomials to the
ideal to force the solutions in $\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 $\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 $\F_2$ by considering the quotient
ring. If $I$ is an ideal in $\F[x_1, ..., x_n]$ then the ideals in the
quotient ring $\F[x_1, ..., x_n]/I$ are in one-to-one correspondence
with the ideals of $\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.

\subsection{Implementation specific notes}

\PolyBoRi comes with a Python wrapper. However this wrapper does not
match \SAGE's style and is written using Boost. Thus \SAGE's wrapper
is a reimplementation of Python bindings to \PolyBoRi's C++
library. This interface is written in Cython like all of \SAGE's C/C++
library interfaces. An interface in \PolyBoRi style is also provided
which is effectively a reimplementation of the official Boost wrapper
in Cython. This means that some functionality of the official wrapper
might be missing from this wrapper and this wrapper might have bugs
not present in the offical Python interface.

\subsection{Access to the original \PolyBoRi interface}

The re-implementation \PolyBoRi's native wrapper is available to the user too:

    sage: from polybori import *
    sage: declare_ring([Block('x',2),Block('y',3)],globals())
    Boolean PolynomialRing in x(0), x(1), y(0), y(1), y(2)
    sage: r
    Boolean PolynomialRing in x(0), x(1), y(0), y(1), y(2)

    sage: [Variable(i) for i in xrange(r.ngens())]
    [x(0), x(1), y(0), y(1), y(2)]

For details on this interface see:

   \url{http://polybori.sourceforge.net/doc/tutorial/tutorial.html}.
    

REFERENCES:
    [BD07] Michael Brickenstein, Alexander Dreyer; '\PolyBoRi: A
    Groebner basis framework for Boolean polynomials';
    http://www.itwm.fraunhofer.de/zentral/download/berichte/bericht122.pdf

File: sage/rings/polynomial/pbori.pyx (starting at line 4124)

Return the currently active global ring, this is only relevant for
the native \PolyBoRi interface.

sage: from polybori import declare_ring, get_cring, Block
sage: R = declare_ring([Block('x',2),Block('y',3)],globals())
sage: Q = get_cring(); Q
Boolean PolynomialRing in x(0), x(1), y(0), y(1), y(2)
sage: R is Q
True

File: sage/rings/polynomial/pbori.pyx (starting at line 1081)

Return a variable mapping between variables of \var{other} and
\var{ring}. When other is a parent object, the mapping defines
images for all variables of other. If it is an element, only
variables occuring in other are mapped.

Raises \code{NameError} if no such mapping is possible.

EXAMPLES:
    sage: P.<x,y,z> = BooleanPolynomialRing(3)
    sage: R.<z,y> = QQ[]
    sage: sage.rings.polynomial.pbori.get_var_mapping(P,R)
    [z, y]
    sage: sage.rings.polynomial.pbori.get_var_mapping(P, z^2)
    [z, None]

    sage: R.<z,x> = BooleanPolynomialRing(2)
    sage: sage.rings.polynomial.pbori.get_var_mapping(P,R)
    [z, x]
    sage: sage.rings.polynomial.pbori.get_var_mapping(P, x^2)
    [None, x]

File: sage/rings/polynomial/pbori.pyx (starting at line 4028)

The opposite of navigating down a ZDD using navigators is to
construct new ZDDs in the same way, namely giving their else- and
then-branch as well as the index value of the new node.

INPUT:
    root -- a variable
    a -- the if branch, a \code{BooleSet} or a \code{BoolePolynomial}
    b -- the else branch, a \code{BooleSet} or a \code{BoolePolynomial}

EXAMPLE:
    sage: from polybori import if_then_else
    sage: B = BooleanPolynomialRing(6,'x')
    sage: x0,x1,x2,x3,x4,x5 = B.gens()
    sage: f0 = x2*x3+x3
    sage: f1 = x4
    sage: if_then_else(x1, f0, f1)
    {{x1,x2,x3}, {x1,x3}, {x4}}

    sage: if_then_else(x1.lm().index(),f0,f1)
    {{x1,x2,x3}, {x1,x3}, {x4}}

    sage: if_then_else(x5, f0, f1)
    Traceback (most recent call last):
    ...
    IndexError: index of root must be less than the values of roots of the branches.

File: sage/rings/polynomial/pbori.pyx (starting at line 4139)

Set the currently active global ring, this is only relevant for the native
\PolyBoRi interface.

sage: from polybori import *
sage: declare_ring([Block('x',2),Block('y',3)],globals())
Boolean PolynomialRing in x(0), x(1), y(0), y(1), y(2)
sage: R = get_cring(); R
Boolean PolynomialRing in x(0), x(1), y(0), y(1), y(2)

sage: declare_ring([Block('x',2),Block('y',2)],globals())
Boolean PolynomialRing in x(0), x(1), y(0), y(1)

sage: get_cring()
Boolean PolynomialRing in x(0), x(1), y(0), y(1)

sage: set_cring(R)
sage: get_cring()
Boolean PolynomialRing in x(0), x(1), y(0), y(1), y(2)

File: sage/rings/polynomial/pbori.pyx (starting at line 4098)

Return the highest index in the parameter \var{s}.

INPUT:
    s -- \code{BooleSet}, \code{BooleMonomial}, \code{BoolePolynomial}

EXAMPLE:
    sage: B.<x,y,z> = BooleanPolynomialRing(3)
    sage: from polybori import top_index
    sage: top_index(x.lm())
    0
    sage: top_index(y*z)
    1
    sage: top_index(x + 1)
    0

File: sage/rings/polynomial/pbori.pyx (starting at line 4164)

Unpickle boolean polynomials

EXAMPLE: 
    sage: T = TermOrder('deglex',2)+TermOrder('deglex',2) 
    sage: P.<a,b,c,d> = BooleanPolynomialRing(4,order=T) 
    sage: loads(dumps(a+b)) == a+b # indirect doctest
    True 

File: sage/rings/polynomial/pbori.pyx (starting at line 4176)

Unpickle boolean polynomial rings.

EXAMPLE: 
    sage: T = TermOrder('deglex',2)+TermOrder('deglex',2) 
    sage: P.<a,b,c,d> = BooleanPolynomialRing(4,order=T) 
    sage: loads(dumps(P)) == P  # indirect doctest
    True