Комбинаторные свойства совершенно уравновешенных булевых функций

• Автор: Смышляев, Станислав Витальевич
• Шифр специальности: 05.13.19
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Москва
• Количество страниц: 164 с. : ил.

Содержание
Введение .

Глава 1. Общие свойства совершенно уравновешенных булевых функций

1.1. Обозначения, определения и общие сведения.

1.2. Методы исследования совершенно уравновешенных булевых функций.

1.3. Распознавание свойства совершенной уравновешенности .

1.4. Совершенная уравновешенность и недопустимые слова во входной последовательности

Глава 2. Барьеры булевых функций

2.1. Понятие барьера булевой функции

2.2. Функции с барьером длины 3 .

2.3. Восстановление символов входной последовательности . .

Глава 3. Функции без предсказывания и локально обратимые функции
3.1. Критерий наличия барьера у булевой функции
3.2. Булевы функции без предсказывания.
3.3. Локачьно обратимые булевы функции
Глава 4. Классы совершенно уравновешенных булевых функций .
4.1. Построение функций из множества РВп П Фп и
4.2. Булевы функции с правым барьером длины 3
4.3. Классы совершенно уравновешенных булевых функций без барьера
Заключение.
Литература


Таким образом, является важной задача разработки математического аппарата для исследования алгебраических, комбинаторных и криптографических свойств совершенно уравновешенных булевых функций, нелинейно зависящих от крайних переменных, а также разработка методов построения классов совершенно уравновешенных функций с определенными положительными криптографическими качествами. Диссертационная работа состоит из четырёх глав, заключения и приложения. Глава 1 посвящена общим свойствам совершенно уравновешенных булевых функций. В разделе 1. Определяется отображение /г :УГ —> Т'г+п-і, описывающее функционирование кодирующего устройства, построенного с помощью регистра сдвига и функции п переменных / в течение г тактов. Раздел 1. В терминах свойств таких множеств доказывается критерий совершенной уравновешенности (Лемма 1. Следствие 1. Кроме того, доказывается утверждение (Теорема 1. Для всякого п > 2 строится широкий класс таких функций. В разделе 1. Наилучший из ранее известных алгоритмов был предложен М. И. Рожковым [6-8) и позволяет распознать совершенную уравновешенность булевой функции за 0(ДГ -2Л/2) операций, где АГ = 2п — длина вектора значений. Данный алгоритм основан па результате о совершенной уравновешенности всякой булевой функции /, для которой верно, что отображение Д(п) является уравновешенным при д(п) = 2П"1. Далее в этом разделе рассматривается утверждение, полученное ранее Й. Голичем ([]) с определенным пробелом в доказательстве, аналогичное утверждению Рожкова, но снижающее ц{п) до величины п. Следовательно, данное утверждение Голича предположительно позволяет построить более быстрый алгоритм распознавания совершенной уравновешенности. В продолжении раздела 1. Теорема 1. Голича. Для построения существенно более быстрого, чем алгоритм М. И. Рожкова, алгоритма распознавания свойства совершенной уравновешенности далее в разделе 1. В терминах графа сдвигов доказывается критерий совершенной уравновешенности булевой функции (Теорема 1. Аг2) операций. Таким образом, впервые получен полиномиальный алгоритм распознавания свойства совершенной уравновешенности по вектору значений. Как следует из результатов С. Н. Сумарокова, символы выходной последовательности кодирующего устройства являются независимыми равномерно распределенными (в предположении, что таковы символы входной последовательности) в том и только в том случае, когда функция усложнения данного кодирующего устройства совершенно уравновешена. В разделе 1. Доказывается Теорема 1. Ранее, за исключением единичных примеров, не было известно каких-либо множеств совершенно уравновешенных функций, нелинейно существенно зависящих от крайних переменных. С целью развития данного направления исследований в главе 2 вводится класс функций с барьером. В разделе 2. Доказывается (Теорема 2. Строится метод, позволяющий получать (с ростом числа переменных) булевы функции со сколь угодно большой длиной барьера. Доказывается утверждение (Теорема 2. В заключение раздела приводится описание строения множества функций с барьером длины 1 (линейные по крайней переменной функции) и 2 (не зависящие существенно от одной из крайних переменных и линейные по соседней с ней). Как следует из результатов раздела 2. В разделе 2. С помощью разработанного аппарата помеченных графов де Брейна формулируется и доказывается критерий наличия у функции правого барьера длины 3 (Теорема 2. Этот критерий позволяет для определения наличия данного свойства у функции переходить от проверки выполнимости системы булевых уравнений к проверке некоторого конечного набора свойств подфункций. Он оказывается удобным для проверки наличия у булевой функции барьера длины 3 — с помощью него далее в разделе 2. Кс. Лэя и Дж. Месси о достаточном условии кодирующего устройства быть 2-обратимым (см. Далее также с помощью полученного критерия наличия у булевой функции барьера длины 3 строится опровержение доказанного (с пробелом в доказательстве) Маркусом Дихтлом неверного результата о необходимом условии совершенной уравновешенности (см. Строится булева функция с барьером длины 3, не удовлетворяющая необходимому условию Дихтла.