Введение
1. Дискретное логарифмирование
1.1 Анализ текущих исследований и обзор алгоритмов
2. Алгоритм Адлемана
2.1 Описание алгоритма
2.2 Пример
2.3 Программная реализация
3. Алгоритм COS
3.1 Описание алгоритма
3.2 Пример
3.3 Программная реализация
4. Алгоритм исчисления порядка
4.1 Описание алгоритма
4.2 Пример
4.3 Ускоренный алгоритм исчисления порядка(УАИП)
4.4 Примеры
4.5 Сравнение оригинального алгоритма и УАИП
4.6 Программная реализация УАИП
5. Вспомогательные алгоритмы и методы
5.1 Расширенный алгоритм Евклида
5.2 Метод Гаусса
6. Другие методы дискретного логарифмирования
6.1 Метод квадратичного решета
7. Исследование результатов работы алгоритмов
Заключение
Список использованной литературы
Приложение
Использование дискретного логарифмирования позволило в последнее время получить множество новых систем информационного обмена. Оптимизация сопутствующих вычислений стала важной задачей. Другая возможность эффективного решения задачи вычисления дискретного логарифма связана с квантовыми вычислениями. Квантовые компьютеры в теории хорошо подходят для нужд машинного обучения. Они манипулируют большими объёмами данных за один проход и способны моделировать нейронную сеть экспоненциального размера. Задача дискретного логарифмирования является одной из основных задач, на которых базируется криптография с открытым ключом. Таким образом, исследование и ускорение алгоритмов дискретного логарифмирования имеют большое значение.
Целью работы является исследование скорости сходимости современных алгоритмов, вычисляющих дискретный логарифм и выбор оптимальных алгоритмов для вычисления дискретного логарифма в конечных полях различной длины, а также усовершенствование алгоритмов, их реализация в среде Visual Studio 2018 на языке С# и проведение сравнительного анализа.
Исходя из цели работы, поставлены следующие задачи:
1. Изучение литературы и сбор данных о проблеме дискретного логарифмирования.
2. Изучение существующих алгоритмов дискретного логарифмирования.
3. Реализация алгоритма дискретного логарифмирования, выбранного в качестве основного, в среде Visual Studio 2018 на языке C#.
4. Реализация других алгоритмов дискретного логарифмирования в среде Visual Studio 2018 на языке C# для последующего сравнительного анализа.
5. Проведение исследования характеристик выполнения алгоритмов (скорость работы в различных ситуациях, сложность реализации).
6. Проведение сравнения алгоритмов на основе полученных ранее данных по скорости работы, сложности реализации, а также алгоритмических принципах и алгоритмической сложности.
7. Сделать выводы о полученных результатах исследования.
В диссертации были исследованы субэкспоненциальные алгоритмы дискретного логарифмирования - Адлемана, COS и исчисления порядка. Дальнейшее развитие получил алгоритм исчисления порядка, в рамках чего был разработан и реализован УАИП, что и является научной новизной работы.
В первой главе было рассмотрено дискретное логарифмирование. Были изучены области человеческой деятельности, в которых применяется дискретное логарифмирование. Так же в этой главе были изучены различные исследования и публикации, которые касаются поставленной задачи.
Вторая глава посвящена изучению и реализации алгоритма Адлемана. Был подробно описан алгоритм, приведены примеры, а также основные пункты в реализации алгоритма Адлемана.
В третьей главе предложено рассмотреть алгоритм COS. Был подробно описан алгоритм, приведены примеры решения задачи дискретного логарифмирования с помощью этого алгоритма, пошагово рассмотрена программная реализация алгоритма COS.
В четвертой главе описан алгоритм исчисления порядка. Был предложен УАИП, приведены примеры. Проведено сравнение оригинального и усовершенствованного алгоритмов, в частности, приведены блок-схемы. Реализован алгоритм УАИП.
В пятой главе рассмотрены вспомогательные алгоритмы и методы, которые применялись при реализации алгоритмов, в частности, метод Гаусса, который был использован для решения систем уравнений, и расширенный алгоритм Евклида для поиска НОД.
В шестой главе проанализированы другие современные алгоритмы дискретного логарифмирования.
В седьмой главе получены результаты экспериментов и сделаны выводы.
В рамках исследования установлено, что разработанный УАИП имеет меньшую вычислительную сложность в сравнении с оригинальным алгоритмом исчисления порядка, что позволяет быстрее решать поставленную задачу на практике, а также не требует длительных и громоздких вычислений. В ходе сравнительного анализа выяснилось, что для чисел a,b,p до 105 лучше всего работает алгоритм УАИП. Это обусловлено тем, что перебор происходит быстрее, чем решение систем уравнений в алгоритмах Адлемана и COS. Для чисел a,b,p больше 105 лучший результат показал алгоритм Адлемана. Это обусловлено тем, что при значениях >105 перебор в алгоритме индекс исчислений работает медленнее, перебор происходит гораздо дольше. Алгоритм COS отстает по причине довольно большой базы, соответственно система уравнений в нем гораздо больше, чем в Алгоритме Адлемана. Таким образом, поставленные задачи выполнены в полном объеме.
Практическая значимость выпускной квалификационной работы состоит в возможности непосредственного использования результатов работы в различных областях, где необходимо вычисление дискретного логарифма - математическое моделирование, криптография, эконометрика, машинное обучение и т.д. Полученные результаты могут быть использованы в оптимизации промежуточных вычислений многих алгоритмов шифрования, в построении математических и экономических моделей, при аппроксимации различных зависимостей. Рекомендуется для чтения спецкурсов по криптографии и эконометрике.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
