Введение 4
1. Теоретические основы и постановка задачи 6
1.1. Эллиптическая кривая в форме Вейерштрасса 6
1.2. Эллиптическая кривая в форме Эдвардса 6
1.3. Постановка задачи 7
2. Анализ сходимости алгоритма Ленстры 8
2.1. Алгоритм факторизации Ленстры для кривой в форме Вейерштрасса 8
2.2. Анализ метода Ленстры, исследование классов эллиптических кривых ... 9
3. Анализ эллиптических кривых. Исследование операций сложения на
эллиптических кривых 15
3.1. Эллиптическая кривая в форме Вейерштрасса 15
3.2. Эллиптическая кривая в форме Эдвардса 16
3.3. Эллиптическая кривая в форме Эдвардса в проективных координатах . 17
3.4. Экспериментальное сравнение скорости сложения точек на разных видах
эллиптических кривых 18
4. Средства разработки и архитектура приложения 19
4.1. Решенные подзадачи 21
5. Оценка результатов факторизации и формулирование выводов 23
5.1. Количество успешных и неуспешных кривых в зависимости от
размерности наименьшего делителя числа 23
5.2. Распределение времени успешного разложения в зависимости от
размерности наименьшего делителя числа 25
Заключение 28
Список литературы 29
Приложения
Купить

Факторизацией натурального числа называется разложение этого числа в произведение простых сомножителей. Эта задача имеет большую вычислительную сложность, поэтому она лежит в основе одного из самых популярных методов криптографии с открытым ключом — метода RSA.
Другой важной проблемой теории чисел является проблема проверки простоты целого числа и построения больших простых чисел.
На сегодняшний день метод эллиптических кривых, или алгоритм Ленстры, — один из самых быстрых методов проверки простоты натуральных чисел и факторизации. Есть и другие: метод квадратичного решета и метод решета числового поля - однако если размерность наименьшего делителя превышает рекордные показатели этих методов, то единственная надежда найти делитель может быть выполнена только с помощью метода эллиптических кривых [1].
В этой работе проводится исследование алгоритма Ленстры как для классического определения эллиптической кривой (кривые Вейерштрасса), так и для кривых в форме Эдвардса. Само исследование заключается в анализе производительности и сходимости алгоритма в зависимости от следующих параметров:
1. количество эллиптических кривых,
2. размерность наименьшего простого делителя числа,
3. тип эллиптических кривых.
Также были выделены и исследованы классы эллиптических кривых.
Теоретическая значимость данной работы заключается в сравнении разных типов эллиптических кривых для достижения лучшей производительности метода Ленстры.
Практическая значимость заключается в формировании модели приложений, в которых предполагается использование метода эллиптических кривых.
В первой главе данной работы раскрываются теоретические основы, необходимые для дальнейшего анализа алгоритма Ленстры.
Во второй главе проводится анализ сходимости метода эллиптических кривых, выявляются необходимые и достаточные требования для сходимости алгоритма, также выделяются классы эллиптических кривых.
В третьей главе проводится анализ самих эллиптических кривых: исследованы отличия в операциях над точками, принадлежащими кривым Вейерштрасса и Эдвардса, и сделаны выводы по производительности вычислений, которые подтверждаются экспериментальными замерами.
В четвертой главе описываются инструменты, которые использовались для разработки системы вычислений, также дается краткий обзор архитектуре приложения.
В пятой главе проводится оценка результатов факторизации, полученных с помощью описанной в четвёртой главе системы, и формируются выводы.

Купить