Nsryjdtyk

I am trying to use SageMath for something that involves a lot of manipulation of boolean polynomials.

Here are some examples of what a coefficient vector is:

 x0*x1*x2 + 1 has coefficient vector 10000001

  x1 + x0 + 1 has coefficient vector 11100000  

      x1 + x0 has coefficient vector 01100000

(x0 is the least significant bit.)

The problem is that Sage's API doesn't seem to encourage direct manipulation of monomials or coefficient vectors, probably because the data structures it uses internally are ZDDs instead of bit arrays.

sage: P

x0*x1*x2 + x0*x1 + x0*x2 + x0 + x1*x2 + x1 + x2 + 1

sage: list(P.set())

[x0*x1*x2, x0*x1, x0*x2, x0, x1*x2, x1, x2, 1]

sage: P.terms()

[x0*x1*x2, x0*x1, x0*x2, x0, x1*x2, x1, x2, 1]

In this code, it appears that the problem is that the endianness is the opposite of what one may expect; which would be with x0 being the least significant bit.

The problem is actually more than that. For example:

#!/usr/bin/env python

from sage.all import *

from sage.crypto.boolean_function import BooleanFunction



# "input_str" is a truth table. 

# Returns a polynomial that has that truth table.

def truth_str_to_poly(input_str):

    # assumes that the length of input_str is a power of two

    num_vars = int(log(len(input_str),2))

    truth_table = 

    # convert string to list of ints expected by BooleanFunction 

    for i in list(input_str):

        truth_table.append(int(i))

    B = BooleanFunction(truth_table)

    P = B.algebraic_normal_form()

    return P



# Return the polynomial with coefficient vector 1,1,...,1.

# (This is neccessary because we can't directly manipulate coef. vectors.)

def super_poly(num_vars):

    input_str = ["0"]*(2**num_vars)

    input_str[0] = "1"

    input_str = "".join(input_str)

    return truth_str_to_poly(input_str)



# Return the coefficient vector of P.

# This is the function that is broken.

def poly_to_coef_str(P, num_vars):

    res = ""

    #for i in super_poly(num_vars).terms():

    for i in list(super_poly(num_vars).set()):

        res += str(P.monomial_coefficient(i))

    return res



num_vars = 3

print(super_poly(num_vars).monomials())



# This should have coefficient vector "01000000" = x0

input_poly = "01010101"

P = truth_str_to_poly(input_poly) # Gives correct result

res = poly_to_coef_str(P, 3)

print(" in:"+input_poly)

print("out:"+res)

Output:

[x0*x1*x2, x0*x1, x0*x2, x0, x1*x2, x1, x2, 1]

 in:01010101

out:00010000

This means that it's not just getting the endianness wrong, it's somehow treating the place value of variables inconsistently.

Is there a better way to do this?