Метод решета числового поля

Решето числового поля (англ. Number Field Sieve, NFS) — это алгоритм факторизации целых чисел, являющийся наиболее эффективным из известных для разложения на множители больших чисел (более 100 десятичных знаков). Относится к классу субэкспоненциальных алгоритмов, то есть его время работы растёт медленнее, чем экспонента от длины числа, но быстрее, чем любой полином. Разработан в конце 1980-х — начале 1990-х годов на основе идей, заложенных в более ранних алгоритмах (метод квадратичного решета, метод факторизации с помощью эллиптических кривых). Решето числового поля лежит в основе большинства рекордов по факторизации больших чисел, включая разложение RSA-240 (240 десятичных знаков) в 2019 году.

История

Предпосылки

До появления решета числового поля основным алгоритмом факторизации больших чисел было квадратичное решето (QS), разработанное Карлом Померанцем в 1981 году. Оно позволяло разлагать числа длиной до 100–110 десятичных знаков, но его сложность росла слишком быстро для чисел большей длины. В 1988 году Джон Поллард предложил идею использования колец целых алгебраических чисел для факторизации, что привело к созданию первой версии решета числового поля — специального решета числового поля (SNFS), предназначенного для чисел специального вида (например, чисел Мерсенна или чисел вида \(a^n \pm b^n\)).

Разработка общего решета

В 1990 году Арьен Ленстра, Хендрик Ленстра и Марк Манассе опубликовали описание общего решета числового поля (GNFS), применимого к произвольным целым числам. Этот алгоритм значительно превзошёл квадратичное решето по производительности для чисел длиной более 100 знаков. В 1993 году было выполнено первое крупное разложение с помощью GNFS — число RSA-129 (129 десятичных знаков), что стало важной вехой в криптоанализе.

Рекорды

С 2000-х годов решето числового поля используется для установления рекордов факторизации. В 2009 году было разложено число RSA-768 (232 десятичных знака), а в 2019 году — RSA-240 (240 знаков). Последний рекорд на 2024 год — разложение числа размером 250 десятичных знаков (829 бит) в 2020 году. Все эти достижения стали возможны благодаря распределённым вычислениям и оптимизациям алгоритма.

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

Основная идея

Решето числового поля основано на методе факторизации с помощью гладких чисел (чисел, все простые множители которых не превышают заданной границы). Алгоритм ищет два различных квадрата по модулю \(n\) (факторизуемого числа), что позволяет найти нетривиальный делитель. Для этого используются два кольца целых алгебраических чисел, порождённых корнями многочленов, связанных с \(n\).

Этапы алгоритма

1. Выбор многочленов. Выбираются два неприводимых многочлена \(f(x)\) и \(g(x)\) с целыми коэффициентами, имеющих общий корень \(m\) по модулю \(n\). Обычно \(f(x)\) имеет небольшие коэффициенты, а \(g(x)\) — линейный многочлен (например, \(g(x) = x - m\)).
2. Просеивание. Для большого набора целых чисел \((a, b)\) (обычно в прямоугольной области) вычисляются значения \(f(a/b)\) и \(g(a/b)\) и проверяется, являются ли они гладкими (то есть разлагаются на простые множители, не превышающие заданную границу). Этот этап — самый ресурсоёмкий и выполняется параллельно на множестве вычислительных узлов.
3. Построение матрицы. Для каждой найденной гладкой пары \((a, b)\) строится вектор показателей степеней простых чисел в разложении \(f(a/b)\) и \(g(a/b)\). Эти векторы образуют разреженную матрицу над полем \(GF(2)\).
4. Решение линейной системы. С помощью методов линейной алгебры (например, алгоритма Видемана или блочного метода Ланцоша) находится нетривиальное решение системы, которое даёт комбинацию пар \((a, b)\), произведение которых является квадратом в обоих кольцах.
5. Извлечение делителя. Из найденных квадратов извлекается квадратный корень в кольцах целых алгебраических чисел, после чего вычисляется наибольший общий делитель \( \gcd(x - y, n) \), где \(x\) и \(y\) — соответствующие целые числа, полученные из квадратов.

Сложность

Время работы решета числового поля оценивается как: \[ \exp\left( \left( \sqrt[3]{\frac{64}{9}} + o(1) \right) (\ln n)^{1/3} (\ln \ln n)^{2/3} \right), \] где \(n\) — факторизуемое число. Для сравнения, квадратичное решето имеет сложность \(\exp\left( (1 + o(1)) \sqrt{\ln n \ln \ln n} \right)\), что делает NFS значительно быстрее для чисел длиной более 100–110 десятичных знаков.

Разновидности

Специальное решето числового поля (SNFS)

Предназначено для чисел специального вида, таких как числа Мерсенна (\(2^p - 1\)), числа Ферма (\(2^{2^k} + 1\)) или числа вида \(a^n \pm b^n\). Для таких чисел можно выбрать многочлены с очень маленькими коэффициентами, что ускоряет просеивание в несколько раз по сравнению с GNFS. SNFS используется для факторизации больших чисел Мерсенна, например, \(M_{1061}\) (1061 бит) было разложено в 2012 году.

Общее решето числового поля (GNFS)

Применяется к произвольным целым числам. Требует более сложного выбора многочленов и большего объёма вычислений, но остаётся единственным практическим алгоритмом для факторизации чисел длиной более 150 знаков.

Применение

Криптоанализ RSA

Основное применение решета числового поля — взлом криптосистемы RSA путём факторизации её модуля. Безопасность RSA основана на сложности разложения больших чисел, и NFS является основным инструментом для оценки этой сложности. Рекомендуемые размеры ключей RSA (2048 бит и более) выбираются с учётом того, что NFS не может разложить такие числа за разумное время с современными вычислительными ресурсами.

Научные исследования

Алгоритм используется для проверки теоретических границ факторизации и тестирования новых вычислительных методов. Рекорды факторизации часто ставятся в рамках распределённых проектов, таких как NFS@Home или BOINC.

Криптография на эллиптических кривых

Хотя NFS не применяется напрямую к эллиптическим кривым, его идеи легли в основу алгоритмов дискретного логарифмирования в полях малой характеристики, что повлияло на выбор параметров для криптосистем на эллиптических кривых.

Критика и ограничения

Вычислительные затраты

Решето числового поля требует огромных вычислительных ресурсов. Для факторизации числа длиной 200 знаков требуется порядка \(10^{20}\) операций, что недоступно для одного компьютера. Распределённые проекты могут занимать месяцы или годы работы тысяч узлов.

Память

Этап решения линейной системы требует хранения разреженной матрицы размером до нескольких миллионов строк и столбцов, что может занимать десятки терабайт оперативной памяти. Это ограничивает применение алгоритма на обычных компьютерах.

Отсутствие доказательства оптимальности

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

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

• Алгоритм был разработан вскоре после того, как в 1988 году Джон Поллард предложил использовать алгебраические числа для факторизации, что стало неожиданностью для криптографического сообщества.
• В 1994 году факторизация RSA-129 с помощью NFS заняла 8 месяцев работы 600 добровольцев, что продемонстрировало уязвимость 512-битных ключей RSA.
• Для факторизации RSA-240 в 2019 году потребовалось около 4000 ядер процессора в течение 2,5 лет, а также 30 терабайт оперативной памяти для решения линейной системы.

Источники

• Lenstra, A. K., Lenstra, H. W., Manasse, M. S., & Pollard, J. M. (1993). The number field sieve. Lecture Notes in Computer Science, 877, 11–42.
• Pomerance, C. (1996). A tale of two sieves. Notices of the AMS, 43(12), 1473–1485.
• Kleinjung, T., et al. (2010). Factorization of a 768-bit RSA modulus. Advances in Cryptology – CRYPTO 2010, 333–350.
• Boudot, F., et al. (2020). Factorization of RSA-240. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2020(4), 1–24.