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

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

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

Алгоритм

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

Случайным образом выбирется эллиптическая кривую $E : y 2 = x 3 + a x + b$ , где $a$ и $b \isin Z$ , и некоторая точка $P = \left({x,y}\right)$ на ней. Если попытка разложения окажется неудачной, следует взять другие $E$ и $P$ и повторить алгоритм сначала.

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

$k = \prod_{l \le B} \ell^{\alpha_i},$

где $\alpha_i = \left\lfloor\log_{\ell} C\right\rfloor$ — наибольший из возможных показателей, при котором $\ell^{\alpha_i} \le C$ .

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

$kP = P \boxplus \dots \boxplus P,$

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

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

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

Литература

Course in number theory and cryptography. — Springer-Verlag, 1987.
Lenstra A. K., Lenstra H. W., Lovász 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. MR 89g:11125.

См. также

Ссылки

Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Полезное

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

Эллиптическая кривая — Не следует путать с Эллипс. Эллиптическая кривая над полем K это множество точек проективной плоскости над K, удовлетворяющих уравнению вместе с точкой на бесконечности. Эллиптические кривые являются одним из основных объектов изучения в… … Википедия
Эллиптическая криптография — раздел криптографии, который изучает асимметричные криптосистемы, основанные на эллиптических кривых над конечными полями. Основное преимущество эллиптической криптографии заключается в том, что на сегодняшний день не существует… … Википедия
Программируемые алгоритмы — Служебный список статей, созданный для координации работ по развитию темы. Данное предупреждение не устанавл … Википедия
Список алгоритмов — Эта страница информационный список. Основная статья: Алгоритм Ниже приводится список алгоритмов, группированный по категориям. Более детальные сведения приводятся в списке структур данных и … Википедия

Словари и энциклопедии на Академике

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