An improved Boolean function class

The boolean_function_improved module defines the BooleanFunctionImproved class, which is a subclass of BooleanFunction that adds extra methods. One such method is cayley_graph, which returns the Cayley graph of the Boolean function.

AUTHORS:

Paul Leopardi (2016-08-23): initial version

EXAMPLES:

sage: from boolean_cayley_graphs.boolean_function_improved import BooleanFunctionImproved
sage: bf = BooleanFunctionImproved([0,0,0,1])
sage: type(bf)
<class 'boolean_cayley_graphs.boolean_function_improved.BooleanFunctionImproved'>
sage: bf.truth_table(format='int')
(0, 0, 0, 1)

class boolean_cayley_graphs.boolean_function_improved.BooleanFunctionImproved[source]

Bases: sage.crypto.boolean_function.BooleanFunction, boolean_cayley_graphs.saveable.Saveable

A subclass of BooleanFunction that adds extra methods.

The class inherits from BooleanFunction is initialized in the same way. The class inherits from Saveable to obtain load_mangled and save_mangled methods.

EXAMPLES:

sage: from boolean_cayley_graphs.boolean_function_improved import BooleanFunctionImproved
sage: bf1 = BooleanFunctionImproved([0,1,0,0])
sage: type(bf1)
<class 'boolean_cayley_graphs.boolean_function_improved.BooleanFunctionImproved'>
sage: bf1.algebraic_normal_form()
x0*x1 + x0
sage: bf1.truth_table()
(False, True, False, False)

TESTS:

sage: from sage.crypto.boolean_function import BooleanFunction
sage: bf = BooleanFunctionImproved([0,1,0,0])
sage: print(bf)
Boolean function with 2 variables

sage: from sage.crypto.boolean_function import BooleanFunction
sage: bf = BooleanFunctionImproved([0,1,0,0])
sage: latex(bf)
\text{\texttt{Boolean{ }function{ }with{ }2{ }variables}}

cayley_graph()[source]

Return the Cayley graph of self.

INPUT:

self – the current object.

OUTPUT:

The Cayley graph of self as an object of class Graph.

EXAMPLES:

sage: from boolean_cayley_graphs.boolean_function_improved import BooleanFunctionImproved
sage: bf1 = BooleanFunctionImproved([0,1,0,0])
sage: g1 = bf1.cayley_graph()
sage: g1.adjacency_matrix()
[0 1 0 0]
[1 0 0 0]
[0 0 0 1]
[0 0 1 0]

extended_cayley_graph()[source]

Return the extended Cayley graph of self.

INPUT:

self – the current object.

OUTPUT:

The extended Cayley graph of self as an object of class Graph. This is the Cayley graph of self if self(0) == False, otherwise it is the Cayley graph of ~self.

EXAMPLES:

sage: from boolean_cayley_graphs.boolean_function_improved import BooleanFunctionImproved
sage: bf1 = BooleanFunctionImproved([0,1,0,0])
sage: g1 = bf1.extended_cayley_graph()
sage: g1.adjacency_matrix()
[0 1 0 0]
[1 0 0 0]
[0 0 0 1]
[0 0 1 0]
sage: bf2 = BooleanFunctionImproved([1,0,1,1])
sage: g2 = bf2.extended_cayley_graph()
sage: g2.adjacency_matrix()
[0 1 0 0]
[1 0 0 0]
[0 0 0 1]
[0 0 1 0]

extended_translate(b=0, c=0, d=0)[source]

Return an extended translation equivalent function of self.

Given the non-negative numbers b, c and d, the function extended_translate returns the Python function

\(x \mapsto \mathtt{self}(x + b) + \langle c, x \rangle + d\),

as described below.

INPUT:

self – the current object.
b – non-negative integer (default: 0) which is mapped to \(\mathbb{F}_2^{dim}\).
c – non-negative integer (default: 0).
d – integer, 0 or 1 (default: 0).

OUTPUT:

The Python function

\(x \mapsto \mathtt{self}(x + b) + \langle c, x \rangle + d\),

where b and c are mapped to \(\mathbb{F}_2^{dim}\) by the lexicographical ordering implied by the base2 function, and where dim is the number of variables of self as a BooleanFunction.

Note

While self is a BooleanFunctionImproved, the result of extended_translate is not a BooleanFunctionImproved, but rather a Python function that takes an Integer argument.

EXAMPLES:

sage: from boolean_cayley_graphs.boolean_function_improved import BooleanFunctionImproved
sage: bf1 = BooleanFunctionImproved([0,1,0,0])
sage: f001 = bf1.extended_translate(b=0,c=0,d=1)
sage: [f001(x) for x in range(4)]
[1, 0, 1, 1]

classmethod from_csv(csv_file_name)[source]

Constructor from a csv file.

The csv file is assumed to be produced by the method save_as_csv().

INPUT:

cls – the class object.
csv_file_name – string: the name of the csv file to read from.

EXAMPLES:

sage: import csv
sage: import os
sage: from boolean_cayley_graphs.boolean_function_improved import BooleanFunctionImproved
sage: bf2 = BooleanFunctionImproved([1,0,1,1])
sage: bf2_csv_name = tmp_filename(ext='.csv')
sage: bf2.save_as_csv(bf2_csv_name)
sage: bf2_test = BooleanFunctionImproved.from_csv(bf2_csv_name)
sage: bf2 == bf2_test
True
sage: os.remove(bf2_csv_name)
sage: bf3 = BooleanFunctionImproved([0,1,0,0]*2)
sage: bf3_csv_name = tmp_filename(ext='.csv')
sage: bf3.save_as_csv(bf3_csv_name)
sage: bf3_test = BooleanFunctionImproved.from_csv(bf3_csv_name)
sage: bf3 == bf3_test
True

classmethod from_tt_buffer(dim, tt_buffer)[source]

Constructor from the buffer tt_buffer.

The buffer tt_buffer is assumed to be the result of method tt_buffer(), which returns a result of type buffer representing a truth table in hex.

INPUT:

cls – the class object.
dim – integer: the dimension of the Boolean function.
tt_buffer – buffer: the result of the method tt_buffer() for the Boolean function.

EXAMPLES:

sage: from boolean_cayley_graphs.boolean_function_improved import BooleanFunctionImproved
sage: bf2 = BooleanFunctionImproved([0,1,0,0])
sage: bf2_tt_buffer = bf2.tt_buffer()
sage: bf2_test = BooleanFunctionImproved.from_tt_buffer(2, bf2_tt_buffer)
sage: bf2_test.algebraic_normal_form()
x0*x1 + x0
sage: bf2 == bf2_test
True
sage: bf3 = BooleanFunctionImproved([0,1,0,0]*2)
sage: bf3.nvariables()
3
sage: bf3_tt_buffer = bf3.tt_buffer()
sage: bf3_test = BooleanFunctionImproved.from_tt_buffer(3, bf3_tt_buffer)
sage: bf3 == bf3_test
True

classmethod from_tt_hex(dim, tt_hex)[source]

Constructor from the dimension dim, and the string tt_hex.

The string tt_hex is assumed to be the result of method tt_hex(), which returns a string representing a truth table in hex.

INPUT:

cls – the class object.
dim – integer: the dimension of the Boolean function.
tt_hex – string: the result of the method tt_hex() for the Boolean function.

EXAMPLES:

sage: from boolean_cayley_graphs.boolean_function_improved import BooleanFunctionImproved
sage: bf2 = BooleanFunctionImproved([0,1,0,0])
sage: bf2_tt_hex = bf2.tt_hex()
sage: bf2_test = BooleanFunctionImproved.from_tt_hex(2, bf2_tt_hex)
sage: bf2_test.algebraic_normal_form()
x0*x1 + x0
sage: bf2 == bf2_test
True

TESTS:

sage: from boolean_cayley_graphs.boolean_function_improved import BooleanFunctionImproved
sage: bf1 = BooleanFunctionImproved([0,1])
sage: bf1_tt_hex = bf1.tt_hex()
sage: bf1_test = BooleanFunctionImproved.from_tt_hex(1, bf1_tt_hex)
sage: bf1_test.algebraic_normal_form()
x
sage: bf1 == bf1_test
True
sage: bf3 = BooleanFunctionImproved([0,1,0,0]*2)
sage: bf3.nvariables()
3
sage: bf3_tt_hex = bf3.tt_hex()
sage: bf3_test = BooleanFunctionImproved.from_tt_hex(3, bf3_tt_hex)
sage: bf3 == bf3_test
True

is_linear_equivalent(other, certificate=False)[source]

Check if there is a linear equivalence between self and other:

\(\mathtt{other}(M x) = \mathtt{self}(x)\),

where M is a GF(2) matrix.

INPUT:

self – the current object.
other – another object of class BooleanFunctionImproved.
certificate – bool (default False). If true, return a GF(2) matrix
that defines the isomorphism.

OUTPUT:

If certificate is false, a bool value. If certificate is true, a tuple consisting of either (False, None) or (True, M), where M is a GF(2) matrix that defines the equivalence.

EXAMPLES:

sage: from boolean_cayley_graphs.boolean_function_improved import BooleanFunctionImproved
sage: bf1 = BooleanFunctionImproved([0,1,0,0])
sage: bf2 = BooleanFunctionImproved([0,0,1,0])
sage: bf1.is_linear_equivalent(bf2)
True
sage: bf2.is_linear_equivalent(bf1, certificate=True)
(
      [0 1]
True, [1 0]
)

linear_code()[source]

Return the Boolean linear code corresponding to self.

INPUT:

self – the current object.

OUTPUT:

An object of class LinearCode representing the Boolean linear code corresponding to self.

EXAMPLES:

sage: from boolean_cayley_graphs.boolean_function_improved import BooleanFunctionImproved
sage: bf2 = BooleanFunctionImproved([0,1,0,0,0,1,0,0,1,0,0,0,0,0,1,1])
sage: bf2.algebraic_normal_form()
x0*x1*x2*x3 + x0*x1 + x0*x2*x3 + x0 + x1*x3 + x2*x3 + x3
sage: c2 = bf2.linear_code()
sage: c2.generator_matrix().echelon_form()
[1 0 0 0 1]
[0 1 0 0 0]
[0 0 1 0 0]
[0 0 0 1 1]

REFERENCES:

save_as_csv(file_name)[source]

Save the current object as a csv file.

INPUT:

self – the current object.
file_name – the file name.

OUTPUT:

None.

EXAMPLES:

sage: import csv
sage: import os
sage: from boolean_cayley_graphs.boolean_function_improved import BooleanFunctionImproved
sage: bf2 = BooleanFunctionImproved([0,1,0,1])
sage: bf2_csv_name = tmp_filename(ext='.csv')
sage: bf2.save_as_csv(bf2_csv_name)
sage: with open(bf2_csv_name) as bf2_csv_file:
....:     reader = csv.DictReader(bf2_csv_file)
....:     for row in reader:
....:         print(row["nvariables"], row["tt_hex"])
....:
2 a
sage: os.remove(bf2_csv_name)

tt_buffer()[source]

Return a buffer containing a compressed version of the truth table.

INPUT:

self – the current object.

OUTPUT:

A buffer containing a compressed version of the truth table of self.

EXAMPLES:

sage: import binascii
sage: from boolean_cayley_graphs.boolean_function_improved import BooleanFunctionImproved
sage: bf2 = BooleanFunctionImproved([0,1,0,0])
sage: buff_bf2 = bf2.tt_buffer()
sage: type(buff_bf2)
<class 'bytes'>
sage: encoding = "UTF-8"
sage: print(str(binascii.b2a_hex(buff_bf2), encoding))
02

TESTS:

sage: bf3 = BooleanFunctionImproved([0,1,0,0,0,1,0,0,1,0,0,0,0,0,1,1])
sage: buff_bf3 = bf3.tt_buffer()
sage: type(buff_bf3)
<class 'bytes'>
sage: encoding = "UTF-8"
sage: print(str(binascii.b2a_hex(buff_bf3), encoding))
c122
sage: from_buff_bf3 = BooleanFunctionImproved.from_tt_buffer(3, buff_bf3)
sage: from_buff_bf3 == buff_bf3
False
sage: from_buff_bf3 == bf3
True
sage: hex_str6 = "0123456789112345678921234567893123456789412345678951234567896123"
sage: bf6 = BooleanFunctionImproved(hex_str6)
sage: buff_bf6 = bf6.tt_buffer()
sage: from_buff_bf6 = BooleanFunctionImproved.from_tt_buffer(6, buff_bf6)
sage: from_buff_bf6 == bf6
True
sage: str(binascii.b2a_hex(buff_bf6), encoding) == hex_str6
True

tt_hex()[source]

Return a hex string representing the truth table of the Boolean function.

INPUT:

self – the current object.

OUTPUT:

A string representing the truth table of self in hex.

EXAMPLES:

sage: import binascii
sage: from boolean_cayley_graphs.boolean_function_improved import BooleanFunctionImproved
sage: bf2 = BooleanFunctionImproved([0,1,0,0])
sage: str_bf2 = bf2.tt_hex()
sage: type(str_bf2)
<class 'str'>
sage: print(str_bf2)
2
sage: bf3 = BooleanFunctionImproved([0,1,0,0,0,1,0,0,1,0,0,0,0,0,1,1])
sage: str_bf3 = bf3.tt_hex()
sage: print(str_bf3)
c122

weight()[source]

Return the Hamming weight of self.

INPUT:

self – the current object.

OUTPUT:

A positive integer giving the number of 1 bits in the truth table of self, in other words, the cardinality of the support of self as a Boolean function.

EXAMPLES:

sage: from boolean_cayley_graphs.boolean_function_improved import BooleanFunctionImproved
sage: bf1 = BooleanFunctionImproved([0,1,0,0])
sage: bf2 = BooleanFunctionImproved([0,1,0,0,0,1,0,0,1,0,0,0,0,0,1,1])
sage: bf1.truth_table()
(False, True, False, False)
sage: bf1.weight()
1
sage: bf2.truth_table(format='int')
(0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1)
sage: sum([int(bf2(x)) for x in range(16)])
5
sage: bf2.weight()
5

zero_translate(b=0, c=0)[source]

Return an extended translation equivalent function of self that is 0 at 0.

Given self and the non-negative numbers b and c, the function zero_translate returns the Python function

\(x \mapsto \mathtt{bf}(x + b) + \langle c, x \rangle + \mathtt{bf}(b)\),

as described below.

INPUT:

self – the current object.
b – non-negative integer (default: 0).
c – non-negative integer (default: 0).

OUTPUT:

The Python function

\(x \mapsto \mathtt{self}(x + b) + \langle c, x \rangle + \mathtt{bf(b)}\),

where b and c are mapped to \(\mathbb{F}_2^{dim}\) by the lexicographical ordering implied by the base2 function, and where dim is the number of variables of self as a BooleanFunction.

Note

While self is a BooleanFunctionImproved, the result of zero_translate is not a BooleanFunctionImproved, but rather a Python function that takes an Integer argument.

EXAMPLES:

sage: from boolean_cayley_graphs.boolean_function_improved import BooleanFunctionImproved
sage: bf1 = BooleanFunctionImproved([0,1,0,0])
sage: f001 = bf1.zero_translate(b=0,c=0)
sage: [f001(x) for x in range(4)]
[0, 1, 0, 0]