Polynomial Boolean Ring

[SSoelvsten]

Introduction

The PolyBoRi library [Brickenstein09] implements Polynomials over the Boolean Ring with ZDDs. To the best of my knowledge, this approach in PolyBoRi is the best approach we have, but it often runs out of memory.

Hence, I believe Adiar may be able to contribute to the area of cryptography by us providing a new class: bp (boolean polynomial). This is a new decision_diagram class that directly resuses many zdd policies. The semantics for bp are: each path in the DAG describe the variables that are multiplied together in a single term. Two different paths correspond to two terms of the polynomial being added together.

Example

Consider the polynomial ac + bc + c which then corresponds to three different paths ac, bc, and c in a ZDD as shown below (Fig. 2 in [Brickenstein09])

       (a)
        | \
       (b) |
        \\ |
         (c)
         / \
       [0] [1]

Operations

The following are sampled from [Brickenstein09], the source code (especially, see the file /libpolybori/include/polybori/BoolePolynomial.h) and my own thoughts.

• [ ] bp_constant(v)

  Equivalent to the zdd_terminal(v) constructor.

  • bp_zero() (result of default constructor)

    Equivalent to the bp_constant(false) constructor.

  • bp_one()

    Equivalent to the bp_constant(true) constructor.

• [ ] bp(const zdd &z) (copy constructor from ZDD)

  Takes a ZDD and interprets it as a boolean polynomial. We do not want to provide an inverse copy-constructor.

• [ ] bp_ithvar(i)

  The ithvar(i) constructor from <adiar/internal/build.h>

• [ ] bp_degree(f)

  A simple top-down traversal that can be done with the counting template algorithm. The only differences are:

  1. The counter is only incremented by one when pushing along the high.
  2. Instead of summing values together when reaching a sink, one takes the maximum instead.

• [ ] bp_lead(f)

  To compute the leading term, we have to report (one of) the longest true paths in the ZDD. Ties between multiple terms with the same degree may be broken lexicographically.

  Assuming every node already stores its own degree, i.e. the length of its deepest path, then this is a simple traversal akin to zdd_maxelem. This value can be maintained within the Reduce operation. Yet, this increases the ZDD size by 1/6th.

  But, otherwise this becomes similar to a simple case of the Linear Optimisation feature proposed above.

• [ ] bp_terms(f)

  Provides an iterator over all terms, i.e. all paths leading to 1. This is similar to the bdd_satall operation requested in #431 .

  • bp_print(f)

    We predefine what to do with the iterator to be printing out each term of the polynomial.

• [ ] bp_add(f,g) (operator: +)

  This is the prod2 algorithm using the same policy (strategy) as for zdd_binop and with the XOR operator.

  • bp_sub(f,g) (operator: -)

    Since we are working over the boolean ring, this is the same as +.

• [ ] bp_mult(f,g) (operator: *)

  The following algorithm is taken from [Brickenstein09]). It essentially distributes into parentheses.

  pbr_mult(f, g):
    if f = 1:
      return g
    if f = 0 or g = 0:
      return 0
    if g = 1 or f = g:
      return f
  
    (f0, f1) = min(f.var, g.var) = f.var ? (f.low, f.high) : (f, f)
    (g0, g1) = min(f.var, g.var) = g.var ? (g.low, g.high) : (g, g)
  
    low = (f0 * g1) + (f1 * g1) + (f1 * g0)
    high = f0 * g0
  
    return (min(f.var, g.var), low, high)
  

  Note: This requires the nested sweeping framework. Furthermore, to resolve low we need three independent recursion requests. So, we would need to further generalise the framework to allow multiple recursion results to be made for the same "direction". One may want to abuse, that + is commutative, and so they do not have to come in the specific order they are declared.

  Note: This seems to be the same as the unate cube product ZDD operation in [Minato01], but where + is not the union operation.

• [ ] bp_div(f,g) (operator: /)

  For division to be well-defined (for anything but 0) one technically needs to work over a field. Yet, that does not mean one cannot divide in a ring, just that one needs to be aware that there are more undefined cases.

  • if g is a monomial:

    This is the unate cube weak division as described in [Minato01], which essentially removes g from all terms and discards terms that do not include at least g (the rest are part of the remainder %)

    pbr_div(f,g):
      if g == 1:
        return f
      if f == 0 or f == 1:
        return 0
    
      if f.var < g.var:
        return (f.var, pbr_div(f.low, g), pbr_div(f.high, g)
    
      v = g.var
      (f0, f1) = f.var == v ? (f.low, g.high) : (f, f)
      (g0, g1) = (g.low, g.high)
    
      if g0 == 0:
        return f1 / g1
      else:
        return zdd_intsec((f0 / f1), (f1 / g1))
    

    This again requires the nested sweeping framework (but this time without any changes).

  • if g is another polynomial:

    If g is zero, throw an error. Otherwise, divide by its leading term (which is a monomial) with respect to the lexicographical order.

• [ ] bp_remainder (operator: %)

  One should be able to design this based on the pbr_div described above. This ought to compute the same result as f - g(f/g) would.

• [ ] bp_divides (operator: |)

  Returns whether the remainder will be non-zero. This might be possible to compute with the pred algorithm (product construction computation of a predicate).

• [ ] bp_gnf(f,G)

  Computes the Greedy Normal Form (see Brickenstein09) of a polynomial f with respect to a finite set G of boolean polynomials.

  bp_gnf(f,G):
    f' = f
    while f' != 0 and some g in G bp_lead(g) | bp_lead(f):
      f' = f' - (f' / bp_lead(g))
    return f'
  

References

• [Brickenstein09] Michael Brickenstein, Alexander Dreyer. “PolyBoRi: A framework for Gröbner-basis computations with Boolean polynomials”. In: Journal of Symbolic Computation. (2009)

[SSoelvsten]

What might be of interest is to look into the Davio Expansion ( see also #442 ). This might have some interesting properties for this domain too.