Метод квадратичного решета

Метод квадратичного решета — это алгоритм факторизации целых чисел, основанный на методе факторизации Ферма и использующий просеивание для нахождения гладких чисел. Он является одним из наиболее эффективных алгоритмов факторизации для чисел размером до 100–110 десятичных знаков (около 330–365 бит) и был разработан в 1981 году американским математиком Карлом Померансом. Метод квадратичного решета (Quadratic Sieve, QS) лежит в основе многих практических реализаций факторизации, включая программу «Msieve» и библиотеку «GMP-ECM».

История

Метод квадратичного решета был предложен Карлом Померансом в 1981 году как улучшение метода факторизации Ферма и алгоритма Диксона. В 1982 году Джеймс Дэвис и Дайан Холдридж реализовали первую компьютерную программу, основанную на QS, которая успешно факторизовала числа длиной до 50 десятичных знаков. В 1994 году с помощью QS было факторизовано 129-значное число RSA-129 (RSA Laboratories — организация, занимающаяся криптографическими исследованиями), что стало важной вехой в истории криптоанализа. Впоследствии метод был усовершенствован: появились варианты с множественным многочленом (MPQS) и специальным квадратичным решетом (SIQS), которые повысили производительность для больших чисел.

Основные принципы

Идея метода Ферма

Метод квадратичного решета основан на идее Пьера Ферма: если число \( N \) можно представить в виде разности квадратов \( N = x^2 - y^2 \), то оно раскладывается на множители как \( (x - y)(x + y) \). Для произвольного \( N \) ищутся такие целые числа \( x \) и \( y \), что \( x^2 \equiv y^2 \pmod{N} \), но \( x \not\equiv \pm y \pmod{N} \). Тогда \( \gcd(x - y, N) \) даёт нетривиальный делитель.

Гладкие числа и факторная база

Ключевым понятием является гладкое число — целое число, все простые делители которого не превышают заданного предела \( B \). Множество простых чисел, не превышающих \( B \), называется факторной базой. Для числа \( N \) выбирается факторная база из всех простых чисел \( p \), для которых символ Лежандра \( \left( \frac{N}{p} \right) = 1 \) (то есть \( N \) является квадратичным вычетом по модулю \( p \)). Это условие необходимо, чтобы многочлен \( Q(x) = x^2 - N \) мог принимать значения, делящиеся на \( p \).

Процедура просеивания

В отличие от метода Диксона, где каждое значение \( Q(x) \) проверяется на гладкость путём пробного деления, QS использует просеивание (sieve). Для каждого простого числа \( p \) из факторной базы находятся решения сравнения \( x^2 \equiv N \pmod{p} \) (обычно два корня \( r_1 \) и \( r_2 \)). Затем для всех \( x \) в интервале просеивания (например, от \( -M \) до \( M \)) к значению \( Q(x) \) прибавляется логарифм \( p \) в тех позициях, где \( x \equiv r_1 \pmod{p} \) или \( x \equiv r_2 \pmod{p} \). После обработки всех простых чисел те позиции, где накопленная сумма превышает порог (например, \( \log N \)), с высокой вероятностью соответствуют гладким числам. Это позволяет избежать полного пробного деления для каждого \( x \).

Алгоритм

Этап 1: Выбор параметров

1. Выбирается факторная база \( B \) — множество простых чисел \( p \leq B_{\max} \), для которых \( \left( \frac{N}{p} \right) = 1 \). Размер базы обычно составляет от нескольких сотен до нескольких тысяч простых чисел.
2. Выбирается интервал просеивания \( M \) (например, \( M \approx B^2 \)). Значения \( x \) берутся из диапазона \( [-M, M] \).
3. Вычисляется многочлен \( Q(x) = x^2 - N \).

Этап 2: Просеивание

Создаётся массив размером \( 2M+1 \), инициализированный нулями. Для каждого простого числа \( p \) из факторной базы:

• Находятся корни \( r_1 \) и \( r_2 \) сравнения \( x^2 \equiv N \pmod{p} \).
• Для каждого \( x \equiv r_1 \pmod{p} \) или \( x \equiv r_2 \pmod{p} \) в интервале \( [-M, M] \) к соответствующему элементу массива прибавляется \( \log p \).

После обработки всех простых чисел элементы массива, превышающие порог \( T \) (обычно \( \log N \)), помечаются как кандидаты в гладкие числа.

Этап 3: Факторизация кандидатов

Для каждого кандидата \( x \) вычисляется \( Q(x) \) и производится пробное деление на все простые числа факторной базы. Если \( Q(x) \) полностью раскладывается на простые множители из базы (т.е. является гладким), то записывается вектор показателей степеней по модулю 2 (так называемый экспонентный вектор). Если \( Q(x) \) не является гладким, оно отбрасывается.

Этап 4: Поиск линейной зависимости

Собирается матрица, строки которой — экспонентные векторы найденных гладких чисел. Требуется найти нетривиальную линейную комбинацию строк, дающую нулевой вектор по модулю 2. Это эквивалентно нахождению набора гладких чисел, произведение которых является полным квадратом. Для решения используется метод Гаусса над полем GF(2) или более эффективные алгоритмы (например, блочный метод Ланцоша или метод Видемана).

Этап 5: Вычисление делителя

Пусть \( S \) — множество индексов, соответствующих найденной линейной зависимости. Вычисляются: \[ X = \prod_{i \in S} x_i \pmod{N}, \quad Y = \prod_{i \in S} \sqrt{Q(x_i)} \pmod{N} \] (где \( \sqrt{Q(x_i)} \) — произведение простых чисел из факторной базы в степенях, равных половине суммы показателей). Если \( X \equiv \pm Y \pmod{N} \), то зависимость тривиальна, и нужно найти другую. Иначе \( \gcd(X - Y, N) \) даёт нетривиальный делитель \( N \).

Варианты метода

Множественное квадратичное решето (MPQS)

Вместо одного многочлена \( Q(x) = x^2 - N \) используется семейство многочленов вида \( Q(x) = ax^2 + 2bx + c \), где \( a \) — квадрат простого числа, \( b^2 \equiv N \pmod{a} \), а \( c = (b^2 - N)/a \). Это позволяет просеивать на разных интервалах, уменьшая размер каждого интервала и ускоряя поиск гладких чисел. MPQS был предложен Питером Монтгомери в 1980-х годах.

Самонеправляемое квадратичное решето (SIQS)

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

Применение

• Криптоанализ RSA: QS применяется для факторизации модулей RSA, состоящих из двух больших простых чисел. Для модулей длиной до 100–110 десятичных знаков QS является наиболее быстрым практическим алгоритмом.
• Тестирование простоты: QS может использоваться для нахождения малых делителей чисел в алгоритмах проверки простоты (например, в тесте Миллера — Рабина).
• Математические исследования: QS применяется для факторизации чисел, возникающих в теории чисел, например, чисел Мерсенна или чисел Ферма.

Преимущества и недостатки

Преимущества

• Высокая скорость для чисел среднего размера (до 100–110 десятичных знаков).
• Простота реализации по сравнению с более сложными алгоритмами, такими как метод решета числового поля (NFS).
• Низкие требования к памяти (порядка нескольких мегабайт для базы и интервала просеивания).

Недостатки

• Экспоненциальная сложность (хотя и субэкспоненциальная): \( O\left( \exp\left( \sqrt{\log N \log \log N} \right) \right) \). Для чисел длиннее 110 десятичных знаков QS уступает методу решета числового поля.
• Чувствительность к выбору параметров (размер базы, интервал просеивания, порог).
• Неэффективен для чисел с очень большими простыми множителями (например, для чисел вида \( p^k \)).

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

• Метод Диксона: QS является его улучшением за счёт просеивания, что сокращает время поиска гладких чисел.
• Метод решета числового поля (NFS): NFS имеет лучшую асимптотическую сложность \( O\left( \exp\left( \sqrt[3]{\log N (\log \log N)^2} \right) \right) \) и эффективен для чисел длиннее 110 десятичных знаков. Однако QS проще в реализации и быстрее для чисел меньшего размера.
• Метод эллиптических кривых (ECM): ECM эффективен для нахождения малых делителей (до 50–60 десятичных знаков), но для полной факторизации больших чисел уступает QS.

Известные факторизации

• RSA-129 (1994): 129-значное число, факторизованное с помощью QS группой исследователей под руководством Арджуна Ленстры. Потребовалось около 8 месяцев работы сети добровольцев.
• RSA-130 (1996): 130-значное число, факторизованное с помощью QS, но уже с использованием MPQS.
• RSA-140 (1999): 140-значное число, для которого QS потребовал около 2 лет работы, что продемонстрировало границы применимости метода.

Источники

• Pomerance, C. (1981). «The Quadratic Sieve Factoring Algorithm». Advances in Cryptology: Proceedings of CRYPTO 84.
• Contini, S. (1997). «Factoring Integers with the Self-Initializing Quadratic Sieve». Master's Thesis, University of Georgia.
• Lenstra, A. K., & Lenstra, H. W. (1993). «The Development of the Number Field Sieve». Springer-Verlag.
• Riesel, H. (1994). «Prime Numbers and Computer Methods for Factorization». Birkhäuser.