Тема: ИССЛЕДОВАНИЕ И УСКОРЕНИЕ АЛГОРИТМОВ ДИСКРЕТНОГО ЛОГАРИФМИРОВАНИЯ В КОНЕЧНОМ ПОЛЕ

Использование дискретного логарифмирования позволило в последнее время получить множество новых систем информационного обмена. Оптимизация сопутствующих вычислений стала важной задачей. Другая возможность эффективного решения задачи вычисления дискретного логарифма связана с квантовыми вычислениями. Квантовые компьютеры в теории хорошо подходят для нужд машинного обучения. Они манипулируют большими объёмами данных за один проход и способны моделировать нейронную сеть экспоненциального размера. Задача дискретного логарифмирования является одной из основных задач, на которых базируется криптография с открытым ключом. Таким образом, исследование и ускорение алгоритмов дискретного логарифмирования имеют большое значение.
Целью работы является исследование скорости сходимости современных алгоритмов, вычисляющих дискретный логарифм и выбор оптимальных алгоритмов для вычисления дискретного логарифма в конечных полях различной длины, а также усовершенствование алгоритмов, их реализация в среде 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 отстает по причине довольно большой базы, соответственно система уравнений в нем гораздо больше, чем в Алгоритме Адлемана. Таким образом, поставленные задачи выполнены в полном объеме.
Практическая значимость выпускной квалификационной работы состоит в возможности непосредственного использования результатов работы в различных областях, где необходимо вычисление дискретного логарифма - математическое моделирование, криптография, эконометрика, машинное обучение и т.д. Полученные результаты могут быть использованы в оптимизации промежуточных вычислений многих алгоритмов шифрования, в построении математических и экономических моделей, при аппроксимации различных зависимостей. Рекомендуется для чтения спецкурсов по криптографии и эконометрике.

Купить