V. G. Nikonov, A. V. Sarantsev, “On the conplexity of joint realization of Boolean functions regular systems in the DNF basis”, Mat. Vopr. Kriptogr., 2010, Volume 1, Issue 3,Pages <nobr>45

This article is cited in 4 papers

On the conplexity of joint realization of Boolean functions regular systems in the DNF basis

V. G. Nikonov^a, A. V. Sarantsev^b

^a Academy of Criptography of Russia, Moscow
^b LLC "Certification Research Center", Moscow

Abstract: Some complexity estimates of joint realization of Boolean functions regular systems in the DNF basis are derived. It is shown that the complexity of joint realization of such systems in the orthogonal DNF basis is equal to its maximal value. A description of functions whiah may be used to generate regular systems of Boolean functions by means of transforms from the Jevons group is given.

Key words: complexity of realisation, DNF, permutation, regular system of Boolean functions.

UDC: 510.52, 512.622

Received 22.IV.2010

DOI: 10.4213/mvk15