Общий метод решета числового поля

Общий метод решета числового поля (англ. General number field sieve, GNFS) — это алгоритм факторизации целых чисел, являющийся наиболее эффективным из известных асимптотических методов для разложения на множители чисел длиной более 100 десятичных знаков. Относится к классам субэкспоненциальных алгоритмов и методов решета. Используется в криптоанализе для взлома криптосистемы RSA, а также в вычислительной теории чисел.

История

Метод был разработан в 1990-х годах как обобщение специального метода решета числового поля (SNFS), который был предложен Джоном Поллардом в 1988 году для факторизации чисел специального вида (например, чисел Мерсенна). Обобщение на произвольные целые числа выполнили математики А. Ленстра, Х. Ленстра, М. Маннассе и Дж. Поллард. Первая успешная реализация GNFS была осуществлена в 1996 году при факторизации 130-значного числа RSA-130.

В 1999 году с помощью GNFS было разложено 155-значное число RSA-155, что потребовало около 8000 MIPS-лет вычислений. В 2020 году группой исследователей под руководством Ф. Бюгра был установлен рекорд: факторизовано 250-значное число (829 бит) с использованием распределённых вычислений.

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

GNFS основан на идее нахождения двух различных представлений одного и того же числа в кольце целых алгебраических чисел. Основные этапы алгоритма:

Выбор полинома

Выбираются два неприводимых многочлена \( f(x) \) и \( g(x) \) с целыми коэффициентами, имеющих общий корень \( m \) по модулю факторизуемого числа \( N \). Обычно используется пара полиномов вида:

• \( f(x) = x^d + c_{d-1}x^{d-1} + \dots + c_0 \)
• \( g(x) = x - m \)

Степень \( d \) выбирается в зависимости от размера \( N \) (обычно от 5 до 7 для чисел до 200 знаков).

Решето

Для всех пар целых чисел \( (a, b) \) в заданной области (обычно \( |a| < L \), \( 0 < b < L \)) проверяется, являются ли значения \( f(a/b) \cdot b^d \) и \( g(a/b) \cdot b \) гладкими числами (то есть разлагаются на простые множители из заданного множества). Процесс решета позволяет быстро отсеивать неподходящие пары.

Сбор соотношений

Найденные гладкие пары \( (a, b) \) порождают соотношения между простыми идеалами в кольцах целых чисел полей \( \mathbb{Q}(\alpha) \) и \( \mathbb{Q}(\beta) \), где \( \alpha \) — корень \( f(x) \), \( \beta \) — корень \( g(x) \). Каждое соотношение имеет вид: \[ \prod_{p \in S} p^{e_p} = \prod_{q \in T} q^{f_q} \] где \( S \) и \( T \) — множества простых идеалов.

Решение линейной системы

Полученные соотношения образуют разреженную систему линейных уравнений над конечным полем \( \mathbb{F}_2 \). Её решение даёт вектор, указывающий, какие соотношения нужно перемножить, чтобы получить квадрат в каждом из полей.

Извлечение квадратного корня

Из найденных квадратов в кольцах целых чисел вычисляются квадратные корни. Затем строится число \( x \) такое, что \( x^2 \equiv y^2 \pmod{N} \). Если \( x \not\equiv \pm y \pmod{N} \), то \( \gcd(x-y, N) \) даёт нетривиальный делитель \( N \).

Асимптотическая сложность

Время работы GNFS оценивается как: \[ L_N[1/3, (64/9)^{1/3}] = \exp\left( \left( \frac{64}{9} \right)^{1/3} (\ln N)^{1/3} (\ln \ln N)^{2/3} \right) \] что составляет примерно \( \exp(1.923 (\ln N)^{1/3} (\ln \ln N)^{2/3}) \). Для сравнения, квадратичное решето имеет сложность \( \exp( (\ln N)^{1/2} (\ln \ln N)^{1/2}) \), что значительно хуже для больших \( N \).

Применение

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

GNFS является основным инструментом для атак на криптосистему RSA. Длина ключа RSA, обеспечивающая безопасность, определяется устойчивостью к GNFS. В 2023 году рекомендуется использовать ключи длиной не менее 2048 бит (617 десятичных знаков), так как факторизация 1024-битных чисел (309 знаков) считается возможной при наличии достаточных вычислительных ресурсов.

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

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

Реализации

Существует несколько программных реализаций GNFS:

• GGNFS — одна из первых открытых реализаций, написанная на C++.
• Msieve — библиотека для факторизации, поддерживающая GNFS.
• CADO-NFS — современная распределённая реализация, разрабатываемая во Франции.
• NFS@Home — проект распределённых вычислений на платформе BOINC, использующий GNFS.

Ограничения

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

Сравнение с другими методами

Критика

Основной недостаток GNFS — сложность реализации и необходимость в большом объёме памяти для хранения разреженных матриц. Кроме того, алгоритм не является детерминированным: существует вероятность неудачи (менее 1%), когда найденные квадраты совпадают по модулю \( N \), что требует повторного запуска с другими параметрами.

Источники

• Lenstra, A. K., Lenstra, H. W., Manasse, M. S., & Pollard, J. M. (1993). The number field sieve. Lecture Notes in Mathematics, 1554, 11–42.
• Buhler, J. P., Lenstra, H. W., & Pomerance, C. (1993). Factoring integers with the number field sieve. Lecture Notes in Mathematics, 1554, 50–94.
• Crandall, R., & Pomerance, C. (2005). Prime Numbers: A Computational Perspective (2nd ed.). Springer.
• Kleinjung, T., et al. (2010). Factorization of a 768-bit RSA modulus. Advances in Cryptology – CRYPTO 2010, 333–350.
• CADO-NFS project documentation. (2023). A distributed implementation of the number field sieve.