Тема: Реализация теста простоты на эллиптических кривых Гольдвассер-Килиана

Тесты числа на простоту играют важнейшую роль в теории чисел, т.к. они связаны с задачей факторизации числа. Самый первый алгоритм на простоту числа был придуман Эратосфеном для того, чтобы эффективно генерировать множество простых чисел от 1 до п за время O(nloglogn). В следствии развития области информационной безопасности и криптографии, в частности криптографии с открытым ключом, важность поиска больших простых чисел возросла. Используя идеи теоремы Ферма, Соловей и Штрассен в 1977 году, и Миллер и Рабин в 1980 году разработали вероятностные тесты простоты. Несмотря на то, что ответ в этих тестах не всегда верен, данные алгоритмы были использованы в криптографии с открытым ключом для построения множества криптосистем таких как RSA, протокол Диффи-Хеллмана, схемы Эль-Гамаля.
Алгоритм Гольдвассер-Килиана использует эллиптические кривые для того, чтобы свести вопрос о простоте числа р, к вопросу о простоте числа q, которое в свою очередь много меньше р. Итерации схемы алгоритма генерируют сертификат, который может быть использован любым, кто хочет удостоверится в простоте числа р.
Цель магистерской диссертации - улучшить алгоритм Гольдвассер- Килиана. Для того чтобы достичь данной цели необходимо решить следующие задачи:
1) Проанализировать теоретический материал, начиная с элементарных понятий из теории чисел.
2) Исследовать алгоритмы для проверки простоты числа.
3) Изучить материал по теории эллиптических кривых, эллиптической арифметике.
4) Выявить основные алгоритмы для вычисления порядка эллиптических кривых.
5) Реализовать алгоритм Гольдвассер-Килиана с использованием алгоритма Шенкса-Местре для подсчета точек на эллиптических кривых.
6) Модифицировать алгоритм Шенкса-Местре.
7) Сравнить и проанализировать «стандартную» и «модифицированную» версии алгоритма.
Новизна работы состоит в следующем:
1) Впервые использован алгоритм Шенкса-Местре в теле алгоритма Г ольдвассер-Килиана
2) Разработана модификация алгоритма Шенкса-Местре
3) Проведено сравнение реализаций

Купить

В данной работе были рассмотрены теоретические и практические вопросы реализации Гольдвассер-Килиана. Разработано консольное приложение, с использованием языка c++, в котором производится тестирование входного числа на простоту методом Гольдвассер-Килиана. Для вычисления порядка кривых был использован алгоритм Шенкса-Местре, который обеспечивает достаточно хорошую сходимость для чисел средней длины. Дополнительно была рассмотрена и реализована модификация алгоритма. Было проведено сравнение и профилирование обеих версий алгоритма с помощью утилиты valgrind. Результаты экспериментов представлены в графическом виде.
Дальнейшим направлением исследования может быть сокращение времени работы алгоритма, затрачиваемого на одну итерацию схемы Гольдвассер-Килиана. Возможные решения: раскрытие внутренних вызовов функций, использование более эффективного алгоритма для вычисления результата скалярного умножения на эллиптической кривой.

Купить