Квадратичное решето

Квадратичное решето — это алгоритм факторизации целых чисел, предназначенный для разложения больших составных чисел на простые множители. Относится к классу методов факторизации с субэкспоненциальной сложностью и является одним из наиболее эффективных алгоритмов для чисел размером до 100–150 десятичных знаков. Квадратичное решето было разработано американским математиком Карлом Померансом в 1981 году на основе идей, восходящих к методу факторизации Ферма и методу непрерывных дробей.

История

Идея факторизации чисел через поиск нетривиальных делителей с помощью разности квадратов была известна ещё Пьеру Ферма в XVII веке. Однако практическая реализация для больших чисел требовала эффективного способа нахождения пар квадратов, сравнимых по модулю факторизуемого числа. В 1970-х годах появился метод факторизации с помощью непрерывных дробей, который использовал разложения в непрерывные дроби для генерации таких пар. В 1981 году Карл Померанс предложил усовершенствование, заменив непрерывные дроби решетом по квадратичным многочленам, что позволило значительно ускорить процесс. В 1994 году алгоритм был успешно применён для факторизации 129-значного числа RSA-129, что стало важной вехой в истории криптоанализа.

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

Квадратичное решето основано на следующем принципе: если для некоторого составного числа \( N \) найти такие целые числа \( x \) и \( y \), что \( x^2 \equiv y^2 \pmod{N} \), но \( x \not\equiv \pm y \pmod{N} \), то \( \gcd(x - y, N) \) и \( \gcd(x + y, N) \) будут нетривиальными делителями \( N \). Задача сводится к поиску достаточного количества сравнений вида \( a^2 \equiv b \pmod{N} \), где \( b \) — гладкое число (то есть разлагающееся только на малые простые множители из заранее выбранного множества — факторной базы). Затем с помощью линейной алгебры над полем \( GF(2) \) комбинируются эти сравнения, чтобы получить полный квадрат в правой части.

Алгоритм

Этап 1: Выбор факторной базы

Факторная база \( B \) — это множество всех простых чисел \( p \), для которых \( N \) является квадратичным вычетом по модулю \( p \), то есть символ Лежандра \( \left(\frac{N}{p}\right) = 1 \). Обычно в базу включают также \( -1 \) и \( 2 \). Размер базы выбирается эмпирически, исходя из размера \( N \).

Этап 2: Процесс решета

Для чисел \( a \) в интервале \( [\sqrt{N} - M, \sqrt{N} + M] \) (где \( M \) — параметр, обычно порядка \( 10^5 \)–\( 10^6 \)) вычисляется значение квадратичного многочлена \( Q(a) = a^2 - N \). Для каждого простого \( p \) из факторной базы решается сравнение \( a^2 \equiv N \pmod{p} \), дающее два корня \( a_1 \) и \( a_2 \). Затем в массиве значений \( Q(a) \) на позициях, соответствующих \( a \equiv a_1 \) или \( a \equiv a_2 \pmod{p} \), значение делится на \( p \) (или вычитается логарифм \( p \), если используется логарифмическое решето). После обработки всех простых чисел из базы те \( a \), для которых остаток от \( Q(a) \) после деления на все простые из базы стал равен 1 (или малому остатку), считаются гладкими. Для каждого такого \( a \) записывается вектор показателей степеней простых чисел в разложении \( Q(a) \).

Этап 3: Линейная алгебра

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

Этап 4: Нахождение делителя

Если найдена комбинация, дающая нулевой вектор, то вычисляется \( x \) как произведение соответствующих \( a \) по модулю \( N \), а \( y \) — как произведение простых чисел из факторной базы в степенях, равных половине суммы показателей. Затем проверяется условие \( x \not\equiv \pm y \pmod{N} \). Если оно выполняется, то \( \gcd(x - y, N) \) даёт нетривиальный делитель \( N \). В противном случае процесс повторяется с другой комбинацией.

Сложность

Асимптотическая сложность квадратичного решета оценивается как \( L_N[1/2, 1] \), где \( L_N[\alpha, c] = \exp\left( (c + o(1)) (\ln N)^\alpha (\ln \ln N)^{1-\alpha} \right) \). Для \( \alpha = 1/2 \) и \( c = 1 \) сложность составляет примерно \( \exp( \sqrt{ \ln N \ln \ln N } ) \). Это делает алгоритм субэкспоненциальным, но для чисел более 150 десятичных знаков он уступает более современным методам, таким как решето числового поля.

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

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

В этой модификации используется несколько квадратичных многочленов вместо одного, что позволяет эффективно распараллелить процесс решета и уменьшить объём памяти. Каждый многочлен имеет вид \( Q(a) = (a + b)^2 - N \), где \( b \) выбирается так, чтобы многочлен имел малые значения на интервале решета.

Самозагружающееся квадратичное решето (SIQS)

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

Применение

Квадратичное решето используется в криптоанализе для взлома RSA-подобных систем, когда размер модуля не превышает нескольких сотен бит. Оно также применяется в теоретико-числовых исследованиях, например, для факторизации чисел специального вида. В 1994 году с помощью квадратичного решета была выполнена факторизация числа RSA-129, что продемонстрировало уязвимость ключей длиной 426 бит. В настоящее время алгоритм реализован во многих библиотеках для работы с большими числами, таких как GMP и PARI/GP.

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

Основным недостатком квадратичного решета является его чувствительность к размеру факторной базы: слишком малая база приводит к недостатку гладких чисел, слишком большая — к неоправданному росту времени на этапе линейной алгебры. Кроме того, алгоритм требует значительного объёма оперативной памяти для хранения массива значений \( Q(a) \), что ограничивает его применение на обычных компьютерах для чисел более 100–120 десятичных знаков. Для чисел с большими простыми множителями (например, RSA-240) квадратичное решето уступает решету числового поля.

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

• Название «квадратичное решето» происходит от использования квадратичного многочлена и процесса решета, аналогичного решету Эратосфена.
• Алгоритм был впервые реализован на практике в 1983 году для факторизации 47-значного числа.
• В 1994 году факторизация RSA-129 заняла около 8 месяцев работы 600 добровольцев, использующих компьютеры по всему миру, и потребовала обработки более 5 миллионов гладких чисел.
• Квадратичное решето является предшественником более мощного решета числового поля, которое используется для факторизации чисел размером до 200–300 десятичных знаков.

Источники

• Pomerance, C. (1981). «The Quadratic Sieve Factoring Algorithm». Advances in Cryptology: Proceedings of EUROCRYPT 84.
• Silverman, R. D. (1987). «The Multiple Polynomial Quadratic Sieve». Mathematics of Computation, 48(177), 329–339.
• Lenstra, A. K., & Lenstra, H. W. (1993). «The Development of the Number Field Sieve». Lecture Notes in Mathematics, 1554.
• Crandall, R., & Pomerance, C. (2005). Prime Numbers: A Computational Perspective. Springer.