Факторизацией натурального числа называется его разложение в произведение простых сомножителей. Данная задача имеет огромную вычислительную сложность. В криптографии один из популярных методов с открытом ключом, метод RSA, который основан на трудоемкости задачи факторизации.
Интерес к эллиптическим кривым появился лишь в прошлом веке, когда Н.Коблиц и В. Миллер предложили использовать ЭК для построении криптографических систем. Далее были найдены приложения инструмента ЭК в разных областях криптографии, так же и для метода факторизации Ленстры . Сложность метода зависит, от наименьшего множителя, а не от самого факторизуемого числа .
В данной работе был исследован алгоритм факторизации Ленстры с использованием эллиптических кривых, являющимся третьим по скорости в мире и имеющим субэкспоненциальную сложность.
Формулы кривых Эдварса, позволяют существенно уменьшить количество элементарных операций при вычислении кратных точки, что приводит к ускорению работы алгоритма. В аффиных координатах нам требуется вычисление обратного элемента, которое влияет на скорость, в случае же проективных этого не требуются.
