RUS  ENG
Full version
JOURNALS // Matematicheskie Voprosy Kriptografii [Mathematical Aspects of Cryptography] // Archive

Mat. Vopr. Kriptogr., 2011 Volume 2, Issue 4, Pages 37–47 (Mi mvk42)

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.

UDC: 519.714.83

Received 23.VI.2010

DOI: 10.4213/mvk42



© Steklov Math. Inst. of RAS, 2025