Fast Computing the Algebraic Degree of Boolean Functions


Бакоев, Валентин (2019) Fast Computing the Algebraic Degree of Boolean Functions In: Ćirić M., Droste M., Pin JÉ. (eds) Algebraic Informatics. CAI 2019. Lecture Notes in Computer Science, vol 11545. Springer, Cham, DOI: 10.1007/978-3-030-21363-3_5 Online ISBN 978-3-030-21363-3, Print ISBN 978-3-030-21362-6 Preprint: Cornell University Library, https://arxiv.org/abs/1905.08649


 Here we consider an approach for fast computing the algebraic degree of Boolean functions. It combines fast computing the ANF (known as ANF transform) and thereafter the algebraic degree by using the weight-lexicographic order (WLO) of the vectors of the n-dimensional Boolean cube. Byte-wise and bitwise versions of a search based on the WLO and their implementations are discussed. They are compared with the usual exhaustive search applied in computing the algebraic degree. For Boolean functions of n variables, the bitwise implementation of the search by WLO has total time complexity $O(n.2^n)$. When such a function is given by its truth table vector and its algebraic degree is computed by the bitwise versions of the algorithms discussed, the total time complexity is $\Theta((9n-2).2^{n-7})=\Theta(n.2^n)$. All algorithms discussed have time complexities of the same type, but with big differences in the constants hidden in the $\Theta$-notation. The experimental results after numerous tests confirm the theoretical results - the running times of the bitwise implementation are dozens of times better than the running times of the byte-wise algorithms.
  Статия
 Boolean function, algebraic normal form, algebraic degree, weight-lexicographic order, WLO sequence generating, byte-wise algorithm, WLO masks generating, bitwise algorithm


Природни науки, математика и информатика Математика
Природни науки, математика и информатика Информатика и компютърни науки

Natural sciences, mathematics and informatics Mathematics
Natural sciences, mathematics and informatics Informatics and Computer Science

 Издадено
  26260
 Валентин Бакоев

Научният архив поддържа инициативата за отворен достъп OAI 2.0 с начален адрес: http://da.uni-vt.bg/oai2/