Алгоритм факторизации Ленстры

Алгоритм факторизации Ленстры (метод эллиптических кривых, ECM) — это субэкспоненциальный алгоритм факторизации целых чисел, основанный на свойствах эллиптических кривых над конечными полями. Разработан голландским математиком Хендриком Ленстрой в 1985 году. Алгоритм особенно эффективен для нахождения небольших (до 50–60 десятичных знаков) простых делителей больших составных чисел, что делает его одним из наиболее распространённых методов для факторизации чисел общего вида.

История

До появления алгоритма Ленстры основными методами факторизации были метод квадратичного решета (QS) и метод Ферма, а также пробное деление. В 1985 году Хендрик Ленстра предложил использовать эллиптические кривые для нахождения делителей, что позволило существенно ускорить процесс по сравнению с классическими алгоритмами. Идея заключалась в адаптации метода факторизации Полларда (p-1) с заменой мультипликативной группы поля на группу точек эллиптической кривой. Это дало возможность работать с числами, для которых метод Полларда был неэффективен из-за больших простых делителей в разложении p-1.

В 1987 году алгоритм был усовершенствован Ричардом Брентом, который предложил модификацию, снижающую вычислительную сложность. С тех пор ECM стал стандартным инструментом в библиотеках для факторизации, таких как GMP-ECM и PARI/GP.

Принцип работы

Алгоритм Ленстры основан на следующей идее: если выбрать случайную эллиптическую кривую над полем вычетов по модулю факторизуемого числа N, то порядок группы точек этой кривой по модулю простого делителя p числа N будет случайным числом, близким к p. Если этот порядок оказывается гладким (то есть разлагается на небольшие простые множители), то можно найти делитель p с помощью вычислений на кривой.

Основные этапы

1. Выбор эллиптической кривой. Случайным образом выбираются коэффициенты a и b кривой вида y² = x³ + ax + b (mod N) и начальная точка P на ней. Кривая должна быть невырожденной (дискриминант не равен нулю по модулю N).

1. Умножение точки на число. Вычисляется k·P, где k — произведение всех простых чисел до некоторой границы B₁, возведённых в соответствующие степени. Это делается с помощью алгоритмов сложения и удвоения точек на эллиптической кривой.

1. Проверка на делитель. В процессе вычислений возникает ситуация, когда операция сложения точек становится невозможной из-за того, что знаменатель оказывается необратимым по модулю N. Это означает, что найден нетривиальный делитель N (как наибольший общий делитель знаменателя и N).

1. Если делитель не найден, граница B₁ увеличивается или выбирается новая кривая, и процесс повторяется.

Стадии алгоритма

Современные реализации ECM включают две стадии:

• Первая стадия (Stage 1). Вычисляется k·P с использованием границы B₁. Если делитель не найден, переходят ко второй стадии.
• Вторая стадия (Stage 2). Ищется делитель среди точек, кратных простым числам от B₁ до B₂. Это увеличивает вероятность успеха при небольшом увеличении времени.

Вычислительная сложность

Сложность алгоритма Ленстры оценивается как O(exp(√(2 ln p ln ln p))) операций, где p — наименьший простой делитель числа N. Эта оценка субэкспоненциальна относительно размера делителя, но не зависит от размера самого числа N. На практике алгоритм наиболее эффективен для делителей размером до 60 десятичных знаков (около 200 бит). Для больших делителей (более 70–80 знаков) предпочтительнее использовать метод решета числового поля (NFS).

Применение

Алгоритм Ленстры широко применяется в следующих областях:

• Криптография. Факторизация чисел используется для взлома криптосистемы RSA. ECM позволяет находить небольшие простые множители в модулях RSA, что может привести к компрометации ключа.
• Теория чисел. Исследование свойств больших чисел, поиск простых делителей чисел Мерсенна, чисел Фибоначчи и других специальных последовательностей.
• Программное обеспечение. ECM входит в состав многих математических пакетов, включая GMP-ECM, PARI/GP, SageMath, Magma. Используется в проектах распределённых вычислений, таких как GIMPS (Great Internet Mersenne Prime Search) и ECMNET.

Примеры

• В 2013 году с помощью ECM был найден простой делитель числа 2^1039 − 1 (числа Мерсенна) размером 53 десятичных знака.
• В проекте ECMNET регулярно находятся делители чисел вида a^n ± 1, используемые в криптографических исследованиях.

Ограничения

• Алгоритм не гарантирует нахождение делителя за конечное время; успех зависит от случайного выбора кривой.
• Для чисел, состоящих только из больших простых делителей (например, произведения двух 100-значных простых чисел), ECM неэффективен.
• Требует большого объёма памяти при работе с большими границами B₁ и B₂.

Интересные факты

• Алгоритм Ленстры является вероятностным: он может не найти делитель даже при его существовании, но вероятность успеха растёт с увеличением числа попыток.
• В 1990-х годах ECM использовался для факторизации чисел, связанных с криптосистемой RSA, что привело к пересмотру рекомендаций по длине ключей.
• Метод эллиптических кривых также применяется в алгоритмах проверки простоты чисел (например, тест Аткина — Морайна).

Критика

Основной недостаток ECM — его чувствительность к размеру наименьшего делителя. Для чисел с большими делителями алгоритм практически бесполезен. Кроме того, реализация требует тщательной оптимизации арифметики больших чисел и управления памятью. Некоторые исследователи отмечают, что ECM уступает методу решета числового поля для факторизации чисел общего вида размером более 100 десятичных знаков.

Источники

• Lenstra, H. W. (1987). "Factoring integers with elliptic curves". Annals of Mathematics. 126 (3): 649–673.
• Brent, R. P. (1986). "Some integer factorization algorithms using elliptic curves". Australian Computer Science Communications. 8: 149–163.
• Montgomery, P. L. (1987). "Speeding the Pollard and elliptic curve methods of factorization". Mathematics of Computation. 48 (177): 243–264.
• Zimmermann, P. (2006). "Implementation of the ECM algorithm". INRIA Research Report.
• Crandall, R.; Pomerance, C. (2005). "Prime Numbers: A Computational Perspective". Springer.