Revision history [back]

Let's first convert this to a BooleanPolynomial. We define a BooleanPolynomialRing:

R.<a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z> = BooleanPolynomialRing(26)

We define a small wrapper class that helps to make the given formula into valid Python code:

class BooleanWrapper:
    _expr = None
    def __init__(self, arg):
        self._expr = arg
    def __pow__(self, exponent):
        return BooleanWrapper(self._expr + exponent._expr)
    def __repr__(self):
        return self._expr.__repr__()
    def __invert__(self):
        return BooleanWrapper(1 - self._expr)
    def __and__(self, other):
        return BooleanWrapper(self._expr * other._expr)
    def __or__(self, other):
        return BooleanWrapper(1 - (1-self._expr)*(1-other._expr))

We also need to preprocess the string a little bit because 0 and 1 are not wrapped:

boolean_str = '(( ~g&(f^i^0))|(g&(1^f^h^0)))^(( ~x&(w^z^0))|(x&(1^w^y^0)))^((d&(1^a^b^e))|( ~d&(1^a^c^e)))^((m&(1^j^k^n))|( ~m&(1^j^l^n)))^o^p^q^0^r^s^t^u^v'
wrapper_vars = {'BooleanWrapper' : BooleanWrapper}
wrapper_vars.update({str(g) : BooleanWrapper(g) for g in R.gens()})
boolean_poly = sage_eval(boolean_str.replace('0', 'BooleanWrapper(0)').replace('1', 'BooleanWrapper(1)'), locals=wrapper_vars)._expr

This gives boolean_poly as

a + b*d + c*d + c + e + f + g*h + g*i + g + i + j + k*m + l*m + l + n + o + p + q + r + s + t + u + v + w + x*y + x*z + x + z

Now we can make this into a boolean function:

from sage.crypto.boolean_function import BooleanFunction
boolean_function = BooleanFunction(boolean_poly)

and finally boolean_function.nonlinearity() gives $31457280$.