Оглавление 2
Введение 3
1. Выбор программных средств 5
2. Об эллиптических кривых 6
2.1 Определение 6
2.2 Операции над точками 6
2.3 Проективные координаты 8
3. Кривые Twisted Edwards 9
4. Алгоритм Ленстры 12
4.1 Описание алгоритма 12
4.2 Анализ метода Ленстры 14
5. Реализация 17
6. Эксперимент с кривыми 18
7. Итоги факторизации 22
Заключение 25
Список литературы 26
Приложение
Купить

Проблема факторизации натурального числа (разложение на простые сомножители) довольно актуальна на сегодняшний день. Предполагается, что факторизация длинных чисел - задача трудоемкая, и на этом предположении основано множество криптосистем. В частности, криптографический алгоритм RSA с открытым ключом имеет в числе своих параметров известное длинное число п, образованное произведением секретных простых чисел p и q (то есть p и q - результат факторизации п).
В статье (1) был опубликован алгоритм RSA-129 и сообщение, зашифрованное с его помощью. Читателям предлагалось расшифровать его, факторизовав 129-значное десятичное число, и получить денежное вознаграждение. На тот момент методов факторизации было немного. Так, метод Ферма справлялся за приемлемое время лишь с числами в 25-30 разрядов. Математическое сообщество взялось за эту задачу, и сейчас существуют такие алгоритмы факторизации:
Экспоненциальные:
- р- и (p-1) - методы Полларда;
- (p+1) - метод Уильямса;
- метод Ленстры;
- методы Шенкса и др;
Субэкспоненциальные:
- метод квадратичного решета (К. Померанс);
- алгоритмы решета числового поля;
- алгоритм Ленстры с использованием эллиптических кривых (ЭК), о котором пойдет речь в данной работе;
- другие.
Цель данной работы - исследование и реализация алгоритма Ленстры факторизации натуральных чисел. Для ее осуществления необходимо решить ряд задач:
- ознакомиться с проблемой факторизации натуральных чисел;
- изучить алгоритм Ленстры на эллиптических кривых;
- реализовать последовательный алгоритм:
- на кривых Вейерштрасса в аффинной и проективной системах координат;
- на кривых Twisted Edwards;
- реализовать параллельную версию алгоритма;
- сравнить скорости работы вышеназванных реализаций и представить результаты;
- исследовать параметры алгоритма.
Купить