Classification of anf graphs for quadratic bent functions in 6 variables.pdf В математике часто возникает задача построения булевых функций, обладающихсвойством нелинейности. Особенный интерес представляют функции, для которых этисвойства экстремальны. Такие булевы функции от четного числа переменных называ-ются бент-функциями. Определим понятие бент-функции более строго. Преобразова-нием Уолша - Адамара булевой функции f от n переменных называется целочислен-ная функция Wf, заданная на множестве Zn равенством Wf (v) = (-1)®f(u).-uezБент-функцией называется булева функция от n переменных (n четно), такая, чтомодуль каждого коэффициента Уолша - Адамара этой функции равен 2n/2.Несмотря на то, что масштабы исследования бент-функций велики, в настоящеевремя они изучены довольно плохо. Например, задача описания всех бент-функцийот n переменных решена лишь при малых значениях n. При n ^ 10 класс бент-функцийне описан, его мощность неизвестна.Обратимся к вопросу классификации бент-функций степени 2 от 6 переменных.Известно [1], что все квадратичные бент-функции аффинно эквивалентны между со-бой. Введем для таких функций понятие более сильной эквивалентности, а именнографовой эквивалентности. Каждой функции сопоставим граф на шести вершинах.Вершины графа отождествим с переменными булевой функции, ребрами соединим тевершины, которые образуют слагаемое в квадратичной части алгебраической нормаль-ной формы (АНФ) функции. Для каждого графа определим его тип - упорядоченныйпо убыванию набор степеней его вершин. Две функции назовем графово эквивалент-ными, если соответствующие им графы изоморфны. В данной работе решена задачаграфовой классификации всех квадратичных бент-функций от 6 переменных.Все квадратичные бент-функции аффинно эквивалентны функции xix2 ф x3x4 ф®x5xg. Поэтому для нахождения графов использовались аффинные преобразованияэтой функции, заданные верхнетреугольными матрицами с 1 на диагонали, 0 или 1над диагональю, а именно вида/ 1 * * * * * \0 1 * * * *0 0 1 * * *0 0 0 1 * * ,0 0 0 0 1 *0 0 0 0 0 1где на местах * стоят 0 или 1. Написана программа на C, которая, перебирая всевозможные матрицы данного вида, определяет типы графов. В результате получено37 типов и 50 графово неэквивалентных бент-функций. В таблице приведены всетипыв левой колонке и соответствующие им бент-функции - в правой. Функция заданавектором лексикографически упорядоченных коэффициентов в квадратичной частиАНФ (в скобках указан возможный способ её построения из бент-функции от четырёхпеременных).№п/пТип Функция1 1 1 1 1 1 1 100000000100001 (iter1)2 2 2 1 1 1 1 100001000100001 (iter1)3 2 2 2 2 11 100001000100101 (iter2)4 3 2 2 1 1 1 100001001001100 (iter1)100001001100001 (iter3)5 3 2 2 2 2 1 1000010011001011000010000101116 3 3 2 2 11 100001001110001 (iter1)100001000110101 (iter2)7 3 3 2 2 2 2 0110010111000011011010011000018 3 3 3 1 1 1 100001010110001 (iter2)9 3 3 3 2 2 1100001001100111 (iter2)10000100111010110000100110011110 3 3 3 3 11100001010110110 (iter2)111001100100001 (iter1)111000000110101 (iter1)11 3 3 3 3 2 211001110010010111010100110010111100100110010110110100110010112 4 2 2 2 11 100001101100001 (iter3)13 4 3 2 2 2 1 100001101100101100001100100111№п/п Тип Функция14 4 3 3 2 11 10000110110001115 4 3 3 2 2 2 11101100010010116 4 3 3 3 2 1 111100001110100 (iter3)17 4 3 3 3 3 2 11001100011011118 4 4 3 2 2 1 10000110110011119 4 4 3 3 11 100001101101110 (iter2)20 4 4 3 3 2 2 11000101111001121 4 4 3 3 3 1 10000110011111122 4 4 3 3 3 3 11101100111010123 4 4 4 3 3 2 01110100111011124 4 4 4 4 3 1 10000110111111125 4 4 4 4 3 3 11100110001011111010110110011126 5 2 2 2 2 1 10000111110000127 5 3 3 2 2 1 10000111110010128 5 3 3 3 2 2 11000100011111129 5 3 3 3 3 3 11010100111111030 5 4 3 3 2 1 10000111111110031 5 4 4 3 2 2 11011100011110132 5 4 4 4 3 2 11110100011111133 5 4 4 4 4 1 10000111111111134 5 5 3 3 3 3 11100110011111135 5 5 4 4 3 3 11100111111101136 5 5 5 4 4 3 11110111111111037 5 5 5 5 5 5 111111111111111Поясним обозначения. Конструкция iterl означает, что к бент-функции от четы-рёх переменных добавляется слагаемое x5x6; iter2 - слагаемое x^5 ф Xjx6, где i , j GG {1, 2, 3, 4}; iter3 - слагаемое xix5 ф x5x6, где i G {1, 2, 3, 4}. Пример: АНФ функции,заданной вектором 100001101100011, имеет вид XiX2 ф X2X3 ф x2x4 ф x2x6 ф X3X4 ф X4X6 ффx5x6. Данное исследование помогает выявить общие закономерности построениябент-функций от (n + 2) переменных с помощью бент-функций от n переменных.

Скачать электронную версию публикации