Факторизация Ленстры с помощью эллиптических кривых

Факторизация Ленстры с помощью эллиптических кривых (англ. elliptic curve factorization method, сокр. ECM) — алгоритм факторизации натурального числа с использованием эллиптических кривых. Данный алгоритм имеет субэкспоненциальное время выполнения. Является третьим по скорости работы после общего метода решета числового поля и метода квадратичного решета.

На практике часто используется для выявления (отбрасывания) небольших простых делителей числа. Если полученное после работы алгоритма число все еще является составным, то остальные сомножители — большие числа. При увеличении количества кривых шансы найти простой сомножитель возрастают, но зависимость количество цифр числа — количество эллиптических кривых экспоненциальна.

Алгоритм

Дано составное целое нечетное число n. Нужно найти его нетривиальный делитель d, 1 < d < n.

Случайным образом выбирется эллиптическая кривую E:y² = x³ + ax + b, где a и , и некоторая точка на ней. Если попытка разложения окажется неудачной, следует взять другие E и P и повторить алгоритм сначала.

1. Выбирается целое число k, делящееся на степени малых простых чисел (не больших некоторого B), не превосходящих C, то есть

где  — наибольший из возможных показателей, при котором .

2. Вычисление kP (все действия производятся по модулю n)

где  — операция сложения, определенная по групповому закону.

Вычисления проводятся до тех пор, пока при попытке найти число, обратное к 2y_p (см. групповой закон) не появляется число, не взаимно простое с n. Это произойдёт при таком k = k₁, что k₁P = O, то есть порядок P в группе E по модулю n является делителем k₁.

3. При применении алгоритма Евклида вместо обращения знаменателя, получаем нетривиальный НОД этого знаменателя и числа n. Он и будет собственным делителем числа n.

Литература

• Course in number theory and cryptography. — Springer-Verlag, 1987.
• Lenstra A. K., Lenstra H. W., Lovasz L. (1982). «Factoring polynomials with rational coefficients». Math. Ann. 261.
• Lenstra Jr., H. W. (1987). «Factoring integers with elliptic curves». Annals of Mathematics 126 (2): 649—673. MR89g:11125.

См. также

• P+1 метод Уильямса
• Факторизация

Ссылки

• http://www.alpertron.com.ar/ECM.HTM
• http://ecm.gforge.inria.fr/