Cand. Sci. (Eng.); аssociate professor at the Cybersecurity and Digital Technologies Institute of the Russian Technological
кандидат технических наук; доцент Института кибербезопасности и цифровых технологий
Dr. Sci. (Eng.), Professor, Member at the Presidium of the Russian Academy of Natural Sciences
доктор технических наук, профессор, член Президиума Российской академии естественных наук.
lecturer
преподаватель
In this paper, a classification study was carried out on the construction of 4-variable Boolean functions representations classification in the form of nonlinearity minimal degree separating surfaces. To construct these surfaces was used an adaptive ellipsoid algorithm based on the Khachiyan algorithm for solving systems of linear inequalities with integer coefficients. To define Boolean functions, we used its graphical representation on the projection of a four-dimensional cube. The classification study carried out was not limited only to the search for a separating surface of the minimum degree of nonlinearity. Additionally, the task was set to find the surface with the smallest number of non-zero nonlinear terms in accordance with a given lexicographic order. Based on the results of the study, a catalog of separating surfaces of the nonlinearity minimum degree with the smallest number of nonlinear terms for Boolean functions of 4 variables is constructed, and it is also determined that 15 classes of geometric equivalence functions have a minimum degree of nonlinearity of 1, 166 - degree 2, 40 - degree 3, and 1 function degree 4.
В работе проведено классификационное исследование по построению представлений булевых функций от 4-х переменных в виде разделяющих поверхностей минимальной степени нелинейности. Для построения этих поверхностей использован адаптивный алгоритм эллипсоидов, основанный на алгоритме Хачияна решения систем линейных неравенств с целочисленными коэффициентами. Для задания булевых функций использовано их графическое представление на проекции четырехмерного куба. Проведенное классификационное исследование не было ограничено только поиском разделяющей поверхности минимальной степени нелинейности. Дополнительно была поставлена задача - найти поверхность с наименьшим числом ненулевых нелинейных членов в соответствии с заданным лексикографическим порядком. По результатам исследования построен каталог разделяющих поверхностей минимальной степени нелинейности с наименьшим числом нелинейных членов для булевых функций от 4-х переменных, а также определено что 15 классов функций геометрической эквивалентности имеют минимальную степень нелинейности 1, 166 - степень 2, 40 - степень 3, и 1 функция степень 4.