Distribution of The Boolean Functions of n Variables According to Their Algebraic Degrees

Valentin Bakoev

Abstract


Knowledge on the enumeration and distribution of
Boolean functions according to their algebraic degrees is
important for the theory as well as for its applications. As of now,
this knowledge is not complete; for example, it is well-known that
half of all Boolean functions have a maximal algebraic degree. In
this paper, a formula for the number of all Boolean functions of n
variables and algebraic degree = k is derived. A direct
consequence from it is the assertion (formulated already by
Claude Carlet) that when n →∞, almost half of all Boolean functions
of n variables have an algebraic degree = n−1. The results
obtained by this formula were used in creating the sequence
A319511 in the OEIS. The discrete probability of a random Boolean
function having a certain algebraic degree is defined and the
corresponding distribution is computed, for 3 ≤ n ≤ 10. Four
applications are considered: at the design and analysis of efficient
algorithms for exact or probabilistic computing the algebraic
degree of Boolean functions; when checking 4 test files for
representativeness; when creating benchmark files of Boolean functions.


Keywords


Boolean function, cryptography, algebraic degree, enumeration, distribution

Full Text: PDF

Refbacks

  • There are currently no refbacks.




ISSN 1314-7897 - Online
ISSN 1312-6555 - Print