Решето числового поля

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

История

Метод был разработан в конце 1980-х — начале 1990-х годов. Его основу заложили Джон Поллард (предложивший общую идею решета в числовых полях) и Хендрик Ленстра (разработавший практическую реализацию). Первая успешная реализация алгоритма была выполнена в 1990 году для факторизации девятого числа Ферма (F9 = 2^512 + 1), состоящего из 155 десятичных знаков. Впоследствии решето числового поля было усовершенствовано, и в 2009 году с его помощью была выполнена факторизация 768-битного RSA-ключа (RSA-768, 232 десятичных знака), что потребовало около двух лет работы распределённой вычислительной сети.

Общая идея

Решето числового поля основано на поиске пар целых чисел (a, b), для которых значения двух многочленов (одного — с целыми коэффициентами, другого — с коэффициентами из кольца алгебраических целых) являются гладкими числами (то есть разлагаются на малые простые множители). Эти пары образуют так называемые «гладкие» соотношения, которые затем используются для построения линейной системы уравнений. Решение этой системы позволяет найти нетривиальный делитель исходного числа N.

Алгоритм состоит из нескольких этапов:

1. Выбор многочленов. Для заданного N подбираются два многочлена f(x) и g(x) с целыми коэффициентами, имеющие общий корень m по модулю N. Обычно f(x) имеет степень d (например, d = 5 или 6 для больших чисел), а g(x) — линейный многочлен: g(x) = x — m.
2. Решето. Для всех пар (a, b) в некоторой области (например, |a| ≤ A, 0 < b ≤ B) вычисляются значения f(a/b) b^d и g(a/b) b. Если оба значения являются гладкими (их разложение на простые множители состоит только из малых простых чисел, входящих в факторную базу), пара (a, b) записывается как соотношение.
3. Линейная алгебра. Из найденных соотношений составляется разреженная матрица. С помощью методов линейной алгебры (например, алгоритма Видемана или метода блочного Ланцоша) находится линейная зависимость между строками матрицы. Это даёт комбинацию соотношений, произведение которых является квадратом в кольце алгебраических целых.
4. Извлечение квадратного корня. Из полученной комбинации извлекается квадратный корень в кольце алгебраических целых. Затем, используя сравнение по модулю N, вычисляется делитель N с помощью алгоритма Евклида.

Классификация

Решето числового поля является субэкспоненциальным алгоритмом, то есть его сложность оценивается как O(exp(c (ln N)^(1/3) (ln ln N)^(2/3))), где c — константа (около 1,9 для общего решета). Существуют две основные разновидности:

• Общее решето числового поля (GNFS). Применяется для произвольных чисел N. Использует многочлены степени d, где d выбирается в зависимости от размера N.
• Специальное решето числового поля (SNFS). Применяется для чисел специального вида (например, чисел Ферма, чисел Мерсенна, чисел вида a^n ± b^n). Оно значительно быстрее общего решета, так как позволяет использовать многочлены малой степени (например, d = 2 или 3).

Применение

Основное применение решета числового поля — криптоанализ. Алгоритм используется для факторизации модулей RSA, что позволяет восстанавливать закрытый ключ. В частности, с его помощью были взломаны ключи длиной до 768 бит. Современные рекомендации по длине ключей RSA (2048 бит и более) основаны на оценке вычислительной сложности решета числового поля.

Кроме криптоанализа, метод применяется в теории чисел для исследования свойств больших чисел, например, для поиска делителей чисел Ферма или Мерсенна.

Ограничения

Решето числового поля требует огромных вычислительных ресурсов. Для факторизации 1024-битного числа (около 309 десятичных знаков) по оценкам потребуется в миллионы раз больше операций, чем для 768-битного. Это делает взлом современных RSA-ключей (2048 бит) практически невозможным при текущем уровне развития вычислительной техники. Кроме того, алгоритм требует значительного объёма оперативной памяти для хранения матрицы и промежуточных данных.

Примеры

• Факторизация RSA-768 (2009 год). Число состояло из 232 десятичных знаков. Работа выполнялась в течение двух лет на кластере из нескольких сотен компьютеров. Общее время вычислений составило около 2·10^19 операций.
• Факторизация девятого числа Ферма (1990 год). Число F9 = 2^512 + 1 было разложено на множители с помощью решета числового поля. Это стало первой успешной практической реализацией алгоритма.

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

• Решето числового поля является развитием более раннего алгоритма — квадратичного решета (QS), который был основным методом факторизации в 1980-е годы. Квадратичное решето имеет сложность O(exp((1 + o(1)) sqrt(ln N ln ln N))) и уступает GNFS для чисел с более чем 100 десятичными знаками.
• В 2020 году была выполнена факторизация 795-битного RSA-ключа (RSA-240) с помощью решета числового поля, что потребовало около 900 ядро-лет вычислений.
• Алгоритм может быть распараллелен: этап решета хорошо подходит для распределённых вычислений, а этап линейной алгебры требует эффективных методов работы с разреженными матрицами.

Критика

Основной критикой решета числового поля является его сложность реализации и высокая ресурсоёмкость. Алгоритм требует тщательного подбора параметров (размер факторной базы, границы решета, степень многочленов), что делает его доступным только для специализированных вычислительных центров. Кроме того, метод не гарантирует успеха: если в ходе решета найдено недостаточно соотношений, алгоритм может не сойтись, и потребуется повторный запуск с изменёнными параметрами.

Источники

• Lenstra, A. K., Lenstra, H. W. (1993). The Development of the Number Field Sieve. Lecture Notes in Mathematics, 1554. Springer.
• 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, LNCS 6223, 333–350.
• RSA Laboratories. (2009). The RSA Factoring Challenge.