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