📄Работа №139020
Тема: Применение эвристических алгоритмов к задачам поиска максимально нелинейных векторных булевых функций
Тип работы
Бакалаврская работа
Предмет
математика и информатика
Объем:
48 листов
Год:
2023
Просмотров:
122
4600
руб.
🛒 Купить работу
Не подходит эта работа?
Закажите новую по вашим требованиям
Узнать цену на написание
Закажите новую по вашим требованиям
Представленный материал является образцом учебного исследования, примером структуры и содержания учебного исследования по заявленной теме. Размещён исключительно в информационных и ознакомительных целях.
Workspay.ru оказывает информационные услуги по сбору, обработке и структурированию материалов в соответствии с требованиями заказчика.
Размещение материала не означает публикацию произведения впервые и не предполагает передачу исключительных авторских прав третьим лицам.
Материал не предназначен для дословной сдачи в образовательные организации и требует самостоятельной переработки с соблюдением законодательства Российской Федерации об авторском праве и принципов академической добросовестности.
Авторские права на исходные материалы принадлежат их законным правообладателям. В случае возникновения вопросов, связанных с размещённым материалом, просим направить обращение через форму обратной связи.
Настоящий учебно-методический информационный материал размещён в ознакомительных и исследовательских целях и представляет собой пример учебного исследования. Не является готовым научным трудом и требует самостоятельной переработки.
📋 Содержание
Аннотация 2
Abstract 3
Введение 6
1 Ограничения наибольшей нелинейности (n,m)-функции алгебры логики .... 7
1.1 Постановка задачи 7
1.2 Верхняя оценка наибольшей нелинейности векторной (n,m)-функции
алгебры логики 12
1.3 Нижние границы наибольшей нелинейности (п^Уфункции алгебры
логики 15
1.4 Таблица границ наибольшей нелинейности векторной (п^^функции
алгебры логики для разных n и m 17
2 Применяемые эвристические методы 20
2.1 Метод Метрополиса 20
2.1.1 Метод Метрополиса для несбалансированной задачи 21
2.1.2 Метод Метрополиса для задачи с учётом ограничения на
сбалансированность 22
2.1.3 Версии метода Метрополиса 22
2.2 Поиск восхождением к вершине 22
2.2.1 Метод поиска путём постепенного восхождения к вершине для задачи
без учёта ограничения на сбалансированность 23
2.2.2 Метод поиска путём постепенного восхождения к вершине для задачи
с учётом ограничения на сбалансированность 24
2.3 Генетический алгоритм 24
2.3.1 Генетический алгоритм для несбалансированной задачи 24
2.3.2 Генетический алгоритм для экстремальной задачи с учётом
ограничения на сбалансированность 26
2.3.3 Вариации генетического алгоритма 27
2.4 Совершенствование используемых эвристических методов 28
3 Результаты работы алгоритмов 29
3.1 Результат работы алгоритмов для несбалансированной задачи 31
3.2 Результат работы алгоритмов для сбалансированной задачи 38
Заключение 44
Список используемой литературы 45
Abstract 3
Введение 6
1 Ограничения наибольшей нелинейности (n,m)-функции алгебры логики .... 7
1.1 Постановка задачи 7
1.2 Верхняя оценка наибольшей нелинейности векторной (n,m)-функции
алгебры логики 12
1.3 Нижние границы наибольшей нелинейности (п^Уфункции алгебры
логики 15
1.4 Таблица границ наибольшей нелинейности векторной (п^^функции
алгебры логики для разных n и m 17
2 Применяемые эвристические методы 20
2.1 Метод Метрополиса 20
2.1.1 Метод Метрополиса для несбалансированной задачи 21
2.1.2 Метод Метрополиса для задачи с учётом ограничения на
сбалансированность 22
2.1.3 Версии метода Метрополиса 22
2.2 Поиск восхождением к вершине 22
2.2.1 Метод поиска путём постепенного восхождения к вершине для задачи
без учёта ограничения на сбалансированность 23
2.2.2 Метод поиска путём постепенного восхождения к вершине для задачи
с учётом ограничения на сбалансированность 24
2.3 Генетический алгоритм 24
2.3.1 Генетический алгоритм для несбалансированной задачи 24
2.3.2 Генетический алгоритм для экстремальной задачи с учётом
ограничения на сбалансированность 26
2.3.3 Вариации генетического алгоритма 27
2.4 Совершенствование используемых эвристических методов 28
3 Результаты работы алгоритмов 29
3.1 Результат работы алгоритмов для несбалансированной задачи 31
3.2 Результат работы алгоритмов для сбалансированной задачи 38
Заключение 44
Список используемой литературы 45
📖 Введение
Векторные булевы функции выступают основной составляющей при разработке криптографических систем. Для обеспечения криптостойкости векторная булева функция должна иметь некоторые показатели. Ключевыми показателями криптостойкости являются нелинейность и сбалансированность. Функции должны обладать этими показателями каждая в отдельности и совместно. Целью выпускной квалификационной работы является описание и оценка работы различных эвристических методов нахождения нелинейных и сбалансированных векторных функций алгебры логики. Необходимо рассмотреть нахождение таких функций с помощью алгоритма поиска путём постепенного восхождения на вершину, с помощью алгоритма имитации отжига, с помощью генетического алгоритма. Приведённые методы уже применялись для нахождения векторных булевых функций, но не сравнивались между собой.
Для достижения поставленной цели необходимо выполнить следующие задачи:
- определить границы максимального отклонения векторной булевой функции от аппроксимирующей прямой линии;
- выявить векторные функции алгебры логики, у которых отклонение от аппроксимирующей линии близко к ранее определённым границам максимального отклонения;
- выявить векторные функции алгебры логики, обладающие сбалансированностью, с отклонением от аппроксимирующей прямой линии, приближающимся к определённым ранее границам;
- построить алгоритм и выполнить сравнительный анализ методов, способствующих реализации указанных выше задач.
Для достижения поставленной цели необходимо выполнить следующие задачи:
- определить границы максимального отклонения векторной булевой функции от аппроксимирующей прямой линии;
- выявить векторные функции алгебры логики, у которых отклонение от аппроксимирующей линии близко к ранее определённым границам максимального отклонения;
- выявить векторные функции алгебры логики, обладающие сбалансированностью, с отклонением от аппроксимирующей прямой линии, приближающимся к определённым ранее границам;
- построить алгоритм и выполнить сравнительный анализ методов, способствующих реализации указанных выше задач.
✅ Заключение
К задачам поиска векторных булевых функций с высокой нелинейностью и поиска сбалансированных векторных булевых функций с высокой нелинейностью были применены эвристические алгоритмы: метод Метрополиса, метод поиска путём постепенного восхождения к вершине, генетический алгоритм и их комбинации. Эти алгоритмы были написаны на языке Java. Также был применён генетический алгоритм Matlab.
Чтобы оценить работу запрограммированных алгоритмов относительно максимально возможного значения нелинейности, были изучены теоретические границы максимальной нелинейности. С помощью исследуемых алгоритмов для случаев п = 5, т = 6 и п = 8, т = 9 удалось уточнить теоретические границы максимальной нелинейности снизу.
По работе алгоритмов для обеих задач максимизации нелинейности векторной булевой функции, с учётом требования сбалансированности и без, была собрана статистика для различных п и т. По ней можно сделать вывод, что лучшей статистикой по найденным функциям обладают комбинированные методы поиска, комбинации генетического алгоритма с методом поиска путём постепенного восхождения к вершине и метод Метрополиса с методом поиска путём постепенного восхождения к вершине. Однако, как стоило ожидать, комбинации алгоритмов имеют наибольшее время работы.
Метод поиска путём постепенного восхождения к вершине для задачи без учёта сбалансированности имеет лучшую статистику по функциям среди некомбинированных алгоритмов. Для задачи с учётом сбалансированности метод поиска путём постепенного восхождения к вершине работает в несколько раз быстрее других алгоритмов и часто ищет функции не хуже, чем комбинированные методы поиска.
Чтобы оценить работу запрограммированных алгоритмов относительно максимально возможного значения нелинейности, были изучены теоретические границы максимальной нелинейности. С помощью исследуемых алгоритмов для случаев п = 5, т = 6 и п = 8, т = 9 удалось уточнить теоретические границы максимальной нелинейности снизу.
По работе алгоритмов для обеих задач максимизации нелинейности векторной булевой функции, с учётом требования сбалансированности и без, была собрана статистика для различных п и т. По ней можно сделать вывод, что лучшей статистикой по найденным функциям обладают комбинированные методы поиска, комбинации генетического алгоритма с методом поиска путём постепенного восхождения к вершине и метод Метрополиса с методом поиска путём постепенного восхождения к вершине. Однако, как стоило ожидать, комбинации алгоритмов имеют наибольшее время работы.
Метод поиска путём постепенного восхождения к вершине для задачи без учёта сбалансированности имеет лучшую статистику по функциям среди некомбинированных алгоритмов. Для задачи с учётом сбалансированности метод поиска путём постепенного восхождения к вершине работает в несколько раз быстрее других алгоритмов и часто ищет функции не хуже, чем комбинированные методы поиска.
ИЛИ
Поиск аналога
📕 Список литературы
🖼 Скриншоты
🛒 Оформить заказ
⚡ Работу высылаем в течении 5 минут после оплаты.