Актуальность проблемы: Криптография — наука, занимающаяся разработкой криптосистем, то есть исследованием математических методов преобразования информации с целью защиты систем от несанкционированного доступа.
В век современных технологий время является очень ценным ресурсом. Поэтому важным показателем работы программы является его скорость вычислений. Процесс увеличения скорости идет в следующих направлениях:
1. Увеличение производительности оборудования. Достигается за счёт использования более мощных процессоров. Главной трудностью в данном подходе является большая трудность изготовления таких процессоров. Ещё одной трудностью является обновление оборудования на всех машинах, что влечёт за собой дополнительные расходы.
2. Распараллеливание программы. Распределение общей работы между разными потоками позволяет уменьшить общее время работы программы. Однако алгоритм поиска коэффициентов Безу является итеративным, и соответственно не подлежит распараллеливании.
3. Уменьшение асимптотической сложности используемого алгоритма. Именно этот подход и будет использован в данной работе. Заключается он в уменьшении числа элементарных операций, используемых алгоритмом. Соотношение Безу — представление наибольшего общего делителя целых
чисел в виде их линейной комбинации с целыми коэффициентами [20, с. 29]. Для случая двух целых чисел А и В и их GCD(A,B) = d — наибольший общий делитель, данное соотношение записывается в следующем виде [25, с. 7]:
Аи + Bv = d (1)
При этом коэффициенты и и v называются коэффициентами Безу. Нахождение коэффициентов Безу может использоваться при решении следующих задач:
1. Решение диофантовых уравнений первой степени вида [9, с. 49]:
2. Решение сравнений первой степени вида [2, с. 68] [36]:
Ах = В (mod т) (3)
3. Поиск обратного элемента в поле — частный случай уравнения (3):
Ах = 1 (mod т) (4)
4. Является основой для некоторых криптографических алгоритмов с
открытым ключом, таких как RSA. [6, с. 438] [27, с. 286]
Алгоритм Евклида — эффективный алгоритм для нахождения наибольшего общего делителя двух целых чисел [7, с. 11] [19, с. 180]. Этот алгоритм итеративный и определяется соотношением [23, с. 26]:
GCD (А, В) = GCD (В, A mod В) (5)
Расширенный алгоритм Евклида — модификация алгоритма Евклида, позволяющая находить коэффициенты Безу. Основной идеей является представление полученного остатка на каждой итерации в виде линейной комбинации исходных чисел А и В.
Основной идеей оптимизации алгоритма поиска коэффициентов Безу будет изменение выбора нового числа, что должно привести к более быстрой сходимости алгоритма и соответственно уменьшению числа итераций.
Главным недостатком подхода, описанного выше, является увеличение нагрузки на одну итерацию, что может привести уменьшению скорости полного алгоритма. Поэтому мы должны также оптимально находить новые значения для следующей итерации.
Объект исследования: сфера криптографии и алгоритмов теории чисел.
Предмет исследования: алгоритм нахождения коэффициентов Безу, его алгоритмическая сложность и схемы для его оптимизации.
Цель магистерской диссертации: исследование схем оптимизации алгоритма поиска коэффициентов Безу, их алгоритмическая сложность и их реализация.
Для достижения поставленной цели в работе сформулированы и решены следующие задачи:
1. Анализ алгоритма поиска коэффициентов Безу.
2. Анализ существующих схем оптимизации для обычного алгоритма Евклида.
3. Построение нового алгоритма поиска коэффициентов Безу на основе изученных схем.
Научная новизна исследования: В данной работе можно выделить 4 пункта новизны:
1. Вывод теоретической оценки сходимости для всех рассмотренных схем оптимизации алгоритма поиска коэффициентов Безу.
2. Математическое описание параллельного аппроксимирующего расширенного алгоритма Евклида, идея которого высказана в работе [21].
3. Программная реализация всех рассмотренных схем оптимизации алгоритма поиска коэффициентов Безу на языке Python 3.
4. Проверка на практике теоретически выведенных схем оптимизации алгоритма поиска коэффициентов Безу.
Объем и структура работы: Магистерская диссертация состоит из введения, трёх глав, заключения, списка использованной литературы и приложения в виде листинга. Объем основного текста составляет 45 страниц машинописного текста.
В первой главе проведен краткий анализ предметной области — исходные обычный и расширенный алгоритмы Евклида. Рассмотрены следующие схемы оптимизации обычного алгоритма Евклида — бинарный, k-арный и аппроксимирующий. Также для всех алгоритмов подсчитано примерное число итераций.
Во второй главе рассматриваются модифицированные расширенные алгоритмы Евклида. Для модификации использовались следующие схемы — k-арный, аппроксимирующий и аппроксимирующий с параллелизацией. Все перечисленные схемы были использованы для анализа.
В третьей главе дано описание программы, использованных библиотек и результаты экспериментов.
Каждая глава заканчивается краткими выводами, а вся работа — заключением.
В работе рассмотрены теоретические и практические вопросы поиска коэффициентов Безу. Разработаны: программа, содержащая реализацию всех рассмотренных схем оптимизации расширенного алгоритма Евклида. Также, в диссертации, для оценивания эффективности оптимизации расширенного алгоритма Евклида проведены эксперименты и показаны результаты.
В результате проведенной работы получены следующие результаты:
• Проведён анализ обычного и расширенного алгоритмов Евклида. Разобраны схемы алгоритмов и проведена оценка их сходимости. Также показаны возможные практические применения алгоритмов.
• Проведён анализ существующих методов оптимизации алгоритма
Евклида. Выбранными оказались: бинарный, k-арный,
аппроксимирующий алгоритмы. Разобраны схемы алгоритмов и проведена оценка их сходимости.
• Проведён анализ бинарного расширенного алгоритма Евклида. Разобрана схема алгоритма и проведена оценка его сходимости. Также были приведены аргументы, почему данный алгоритм не рассматривается в этой работе.
• Проведён анализ методов оптимизации алгоритма Евклида. Выбранными оказались: k-арный, аппроксимирующий алгоритмы. Представлены их модификации для расширенного алгоритма Евклида. Рассмотрены возможные исключительные ситуации и разобраны способы их решения. Разобраны схемы алгоритмов и проведена оценка их сходимости.
• Проведён анализ параллельного расширенного алгоритма Евклида. Разобрана схема алгоритма и проведена оценка его сходимости.
• Реализованы все разобранные схемы оптимизации алгоритма Евклида. Протестированы на практике корректность работы полученных реализаций.
• Реализованы все разобранные схемы оптимизации расширенного алгоритма Евклида. Протестированы на практике корректность работы полученных реализаций.
• Реализована программа для проведения экспериментов. Временные характеристики алгоритмов, полученные в ходе программы, сохраняются в файлах.
• Проведён анализ полученных характеристик. Получено графическое отображение результатов.
В ходе работы были сделаны следующие выводы по рассмотренным схемам:
• K-арный — показал наихудший результат среди всех рассмотренных схем. При маленьких значениях модуля количество шагов оказалось больше, чем у оригинального, при больших появился значительный выигрыш. Количество работы на одной итерации при небольшом модуле меньше, чем у других схем, но больше, чем у оригинального алгоритма. Это приводит к суммарному проигрышу во времени для всего алгоритма по сравнению с оригинальным.
• Аппроксимирующий — показал наилучший результат среди всех рассмотренных схем. Количество шагов в разы уменьшилось по сравнению с оригинальным алгоритмом. При больших значениях модуля совпадает по количеству шагов с параллельным. Количество работы на одной итерации при небольшом модуле меньше, чем у параллельного, но больше, чем у оригинального алгоритма. Однако при больших значениях дисперсия становится слишком большой, что усложняет анализ. Одной из причин может быть неоднородная сходимость алгоритма на дробях Фарея.
• Параллельный — количество шагов в разы уменьшилось по сравнению с оригинальным алгоритмом. При больших значениях модуля совпадает по количеству шагов с аппроксимирующим. Количество работы на одной итерации при небольшом модуле самое большое по сравнению с другими алгоритмами. Однако при больших значениях дисперсия становится слишком большой, что усложняет анализ. Одной из причин может быть неоднородная сходимость алгоритма на дробях Фарея.
Дальнейшим направлением исследования возможно уменьшение времени работы, затраченной на одной итерации. Среди возможных подходов: раскрытие внутренних вызовов функций, использование более низкоуровневого языка, использование более быстрого алгоритма подбора коэффициентов.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
