📄Работа №59339
Тема: ВЕКТОРНЫЕ БУЛЕВЫ ФУНКЦИИ ВЫСОКОЙ НЕЛИНЕЙНОСТИ
Тип работы
Бакалаврская работа
Предмет
информатика
Объем:
29 листов
Год:
2016
Просмотров:
161
4380
руб.
🛒 Купить работу
Не подходит эта работа?
Закажите новую по вашим требованиям
Узнать цену на написание
Закажите новую по вашим требованиям
Представленный материал является образцом учебного исследования, примером структуры и содержания учебного исследования по заявленной теме. Размещён исключительно в информационных и ознакомительных целях.
Workspay.ru оказывает информационные услуги по сбору, обработке и структурированию материалов в соответствии с требованиями заказчика.
Размещение материала не означает публикацию произведения впервые и не предполагает передачу исключительных авторских прав третьим лицам.
Материал не предназначен для дословной сдачи в образовательные организации и требует самостоятельной переработки с соблюдением законодательства Российской Федерации об авторском праве и принципов академической добросовестности.
Авторские права на исходные материалы принадлежат их законным правообладателям. В случае возникновения вопросов, связанных с размещённым материалом, просим направить обращение через форму обратной связи.
Настоящий учебно-методический информационный материал размещён в ознакомительных и исследовательских целях и представляет собой пример учебного исследования. Не является готовым научным трудом и требует самостоятельной переработки.
📋 Содержание
Введение 2
1 Постановка задачи 3
2 Границы максимальной нелинейности булевой
(л.; т)-функции 6
2.1 Ограничения сверху 6
2.2 Ограничения снизу 8
2.3 Таблица ограничений на максимальную нелинейность N(n;m) 9
3 Описания используемых алгоритмов поиска 10
3.1 Алгоритм имитации отжига 10
3.1.1 Алгоритм имитации отжига для задачи без ограничений 11
3.1.2 Алгоритм имитации отжига для сбалансированной задачи 11
3.1.3 Модификации 12
3.2 Алгоритм восхождения на вершину 12
3.2.1 Алгоритм восхождения на вершину для задачи без ограничений 12
3.2.2 Алгоритм восхождения на вершину для сбалансированной задачи 13
3.3 Генетический алгоритм 13
3.3.1 Генетический алгоритм для задачи без ограничений 13
3.3.2 Генетический алгоритм для сбалансированной задачи 14
3.3.3 Модификации 15
3.4 Общая модификация для всех алгоритмов 15
4 Результаты работы алгоритмов 15
4.1 Результат работы алгоритмов для задачи без ограничений 17
4.2 Результат работы алгоритмов для сбалансированной задачи 21
Заключение
Список литературы
1 Постановка задачи 3
2 Границы максимальной нелинейности булевой
(л.; т)-функции 6
2.1 Ограничения сверху 6
2.2 Ограничения снизу 8
2.3 Таблица ограничений на максимальную нелинейность N(n;m) 9
3 Описания используемых алгоритмов поиска 10
3.1 Алгоритм имитации отжига 10
3.1.1 Алгоритм имитации отжига для задачи без ограничений 11
3.1.2 Алгоритм имитации отжига для сбалансированной задачи 11
3.1.3 Модификации 12
3.2 Алгоритм восхождения на вершину 12
3.2.1 Алгоритм восхождения на вершину для задачи без ограничений 12
3.2.2 Алгоритм восхождения на вершину для сбалансированной задачи 13
3.3 Генетический алгоритм 13
3.3.1 Генетический алгоритм для задачи без ограничений 13
3.3.2 Генетический алгоритм для сбалансированной задачи 14
3.3.3 Модификации 15
3.4 Общая модификация для всех алгоритмов 15
4 Результаты работы алгоритмов 15
4.1 Результат работы алгоритмов для задачи без ограничений 17
4.2 Результат работы алгоритмов для сбалансированной задачи 21
Заключение
Список литературы
📖 Введение
Векторные булевы функции являются одним из ключевых компонент в криптосистемах. Для того чтобы обеспечить устойчивость против криптографических атак, векторная булева функция должна обладать определенными свойствами. Из набора требуемых свойств нас будут интересовать высокая нелинейность и сбалансированность. Данные свойства мы будем требовать от функций как в отдельности, так и совместно.
В данной работе мы опишем и оценим работу нескольких эвристических методов поиска хороших векторных булевых функций: генетический алгоритм, алгоритм имитации отжига, алгоритм восхождения на вершину. Большинство этих методов уже применялось для поиска функций с высокой нелинейностью и сбалансированностью, однако, насколько нам известно, никто не проводил сравнительные анализ их работы.
Кроме того, найдем верхние и нижние границы максимальной нелинейности булевых функций, чтобы оценивать работу алгоритмов не только относительно друг друга, но и относительно максимально возможного значения нелинейности.
Поставим следующие цели и задачи:
1. Построить и уточнить границы максимальной нелинейности;
2. Найти векторные булевы функции с нелинейностью, приближающейся к границам максимальной нелинейности;
3. Найти сбалансированные векторные булевы функции с нелинейностью, приближающейся к границам максимальной нелинейности;
4. Запрограммировать и сопоставить методы, способствующие достижению этой цели
В данной работе мы опишем и оценим работу нескольких эвристических методов поиска хороших векторных булевых функций: генетический алгоритм, алгоритм имитации отжига, алгоритм восхождения на вершину. Большинство этих методов уже применялось для поиска функций с высокой нелинейностью и сбалансированностью, однако, насколько нам известно, никто не проводил сравнительные анализ их работы.
Кроме того, найдем верхние и нижние границы максимальной нелинейности булевых функций, чтобы оценивать работу алгоритмов не только относительно друг друга, но и относительно максимально возможного значения нелинейности.
Поставим следующие цели и задачи:
1. Построить и уточнить границы максимальной нелинейности;
2. Найти векторные булевы функции с нелинейностью, приближающейся к границам максимальной нелинейности;
3. Найти сбалансированные векторные булевы функции с нелинейностью, приближающейся к границам максимальной нелинейности;
4. Запрограммировать и сопоставить методы, способствующие достижению этой цели
✅ Заключение
К задачам поиска векторных булевых функций с высокой нелинейностью и поиска сбалансированных векторных булевых функций с высокой нелинейностью были применены эвристические алгоритмы — алгоритм имитации отжига, алгоритм восхождения на вершину, генетический алгоритм и их комбинации. Все алгоритмы были запрограммированы на языке Java. Кроме того, к данным задачам был применен встроенный генетический алгоритм Matlab.
Ко всем алгоритмам был предложен и протестирован набор модификаций, после чего было принято решение о применении или неприменении каждой каждой модификации.
Чтобы оценить работу запрограммированных алгоритмов относительно максимально возможного значения нелинейности, были изучены теоретические границы максимальной нелинейности.
С помощью исследуемых алгоритмов для случаев n= 5, m= 6 и n= 8, m= 9 удалось уточнить теоретические границы максимальной нелинейности снизу.
По работе алгоритмов для обеих задач максимизации нелинейности векторной булевой функции, с учетом требования сбалансированности и без, была собрана статистика для различных n и m. По ней можно сделать вывод, что лучшей статистикой по найденным функциям обладают комбинированные методы поиска, комбинации генетического алгоритма с восхождением на вершину и имитации отжига с восхождением на вершину. Однако, как стоило ожидать, комбинации алгоритмов имеют наибольшее время работы.
Также выделим алгоритм восхождения на вершину, который для задачи без учета сбалансированности имеет лучшую статистику по функциям среди некомбинированных алгоритмов. Для задачи с учетом сбалансированности восхождение на вершину всегда работает в несколько раз быстрее других алгоритмов и часто ищет функции не хуже, чем комбинированные методы поиска.
Ко всем алгоритмам был предложен и протестирован набор модификаций, после чего было принято решение о применении или неприменении каждой каждой модификации.
Чтобы оценить работу запрограммированных алгоритмов относительно максимально возможного значения нелинейности, были изучены теоретические границы максимальной нелинейности.
С помощью исследуемых алгоритмов для случаев n= 5, m= 6 и n= 8, m= 9 удалось уточнить теоретические границы максимальной нелинейности снизу.
По работе алгоритмов для обеих задач максимизации нелинейности векторной булевой функции, с учетом требования сбалансированности и без, была собрана статистика для различных n и m. По ней можно сделать вывод, что лучшей статистикой по найденным функциям обладают комбинированные методы поиска, комбинации генетического алгоритма с восхождением на вершину и имитации отжига с восхождением на вершину. Однако, как стоило ожидать, комбинации алгоритмов имеют наибольшее время работы.
Также выделим алгоритм восхождения на вершину, который для задачи без учета сбалансированности имеет лучшую статистику по функциям среди некомбинированных алгоритмов. Для задачи с учетом сбалансированности восхождение на вершину всегда работает в несколько раз быстрее других алгоритмов и часто ищет функции не хуже, чем комбинированные методы поиска.
ИЛИ
Поиск аналога
📕 Список литературы
🛒 Оформить заказ
⚡ Работу высылаем в течении 5 минут после оплаты.