|
On the number of significant variables of balanced Boolean function with the fixed number of elementary conjunctions in its DNF
V. G. Nikonov Academy of Cryptography of Russian Federation, Moscow
Abstract:
The upper and lower bounds for the number $n(k)$ of significant variables of balanced Boolean function represented by $k$ elementary conjunction are obtained. The boundedness of $n(k)$ for every $k$ was proved by the author previously. Balanced Boolean functions are very important for cryptography; their DNF representations correspond to realizations by circuits, in particular, by programmable logical matrices.
Key words:
Boolean function, DNF (disjunctive normal form), Fibonacci numbers.
Received 23.VI.2010
Citation:
V. G. Nikonov, “On the number of significant variables of balanced Boolean function with the fixed number of elementary conjunctions in its DNF”, Mat. Vopr. Kriptogr., 2:4 (2011), 37–47
Linking options:
https://www.mathnet.ru/eng/mvk42https://doi.org/10.4213/mvk42 https://www.mathnet.ru/eng/mvk/v2/i4/p37
|
Statistics & downloads: |
Abstract page: | 567 | Full-text PDF : | 503 | References: | 56 | First page: | 4 |
|