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

Общий метод решета числового поля (англ. general number field sieve, GNFS) — метод факторизации целых чисел. Является наиболее эффективным алгоритмом факторизации чисел длиной более 110 десятичных знаков. Сложность алгоритма оценивается эвристической формулой^[1]

${\displaystyle \exp \left(\left({\sqrt[{3}]{\frac {64}{9}}}+o(1)\right)(\log n)^{\frac {1}{3}}(\log \log n)^{\frac {2}{3}}\right)=L_{n}\left[{\frac {1}{3}},{\sqrt[{3}]{\frac {64}{9}}}\right]}$

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

В 1988 году английский математик Джон Поллард^[англ.] описал новый метод факторизации целых чисел специальной формы (${\displaystyle 2^{n}\pm C}$), проиллюстрировав его разложением седьмого числа Ферма ${\displaystyle F_{7}=2^{128}+1}$. В отличие от метода квадратичного решета, в котором просеивание выполняется в кольце всех целых чисел, в методе предлагалось использовать кольцо целых чисел ${\displaystyle Z([2^{3/2}])}$ над числовым полем ${\displaystyle Q(2^{3/2})}$. Рукопись была приложена к письму, адресованному Эндрю Одлыжко^[англ.], также копии получили Ричард Брент, Джон Бриллхарт^[англ.], Хендрик Ленстра, Клаус Шнорр^[англ.] и Х. Суяма. В этом письме Поллард предположил, что возможно этот метод может быть использован для разложения девятого числа Ферма.^[2]

В 1990 году А. Ленстра, Х. Ленстра, Марк Манассе и Поллард описали первую крупномасштабную реализацию нового метода с некоторыми усовершенствованиями. Они показали, что на числах специального вида алгоритм работает быстрее, чем все остальные известные методы факторизации. Также в работе обсуждается идея Джо Бухлера и Карла Померанса об усовершенствовании метода для разложения любых целых чисел и приводятся наброски решения этой задачи.^[3]

Позднее Леонард Макс Адлеман предложил использовать квадратичный характер для нахождения квадратов в числовом поле. Это предоставило альтернативное решение проблемы, поднятой Бухлером и Померансом, и улучшило предположительное время работы решета числового поля в применении к числам не специального вида.^[4]

В том же году А. Ленстра, Х. Ленстра, Манассе и Поллард представили разложение девятого числа Ферма с помощью метода числового поля. В соответствующей работе обсуждаются многие детали этого разложения.^[5]

Наконец, в работе «Факторизация целых чисел с помощью решета числового поля» Бухлер, Х. Ленстра и Померанс описали метод решета числового поля в применении к числам, которые не обязательно имеют специальный вид.^[6] Эта реализация алгоритма содержала шаг, предполагающий вычисления с использованием чрезвычайно больших чисел. Джин-Марк Кувейгнес в своей работе описал способ обойти это.^[7]

Итоги раннего развития метода подвёл сборник статей под редакций А. Ленстры и Х. Ленстры.^[8] В том числе сборник включал статью Бернштейна и А. Ленстры, описывающую очередную улучшенную реализацию алгоритма. Статья вошла в сборник под заголовком «Общий метод решета числового поля».^[9]

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

• Метод факторизации Ферма для факторизации натуральных нечетных чисел n, состоящий в поиске таких целых чисел x и y, что ${\displaystyle x^{2}-y^{2}=n}$, что ведет к разложению ${\displaystyle n=(x-y)\cdot (x+y)}$.
• Нахождение подмножества множества целых чисел, произведение которых — квадрат^[10]
• Составление факторной базы: набора ${\displaystyle \{-1,p_{1},p_{2},\dots ,p_{n}\}}$, где p_i — простые числа, такие, что ${\displaystyle p_{i}\leqslant B}$ для некоторого B.
• Просеивание выполняется подобно решету Эратосфена (откуда метод и получил своё название). Решетом служат простые числа факторной базы и их степени. При просеивании число не «вычёркивается», а делится на число из решета. Если в результате число оказалось единицей, то оно B-гладкое.
• Основная идея состоит в том, чтобы вместо перебора чисел и проверки, делятся ли их квадраты по модулю n на простые числа из факторной базы, перебираются простые числа из базы и сразу для всех чисел вида ${\displaystyle x^{2}-n}$ проверяется, делятся ли они на это простое число или его степень.

Пусть ${\displaystyle n}$ — нечетное составное число, которое требуется факторизовать.

1. Выберем степень неприводимого многочлена ${\displaystyle d\geq 3}$ (при ${\displaystyle d=2}$ не будет выигрыша в сравнении с методом квадратичного решета).
2. Выберем целое ${\displaystyle m}$ такое, что ${\displaystyle \lfloor n^{1/(d+1)}\rfloor <m<\lfloor n^{1/d}\rfloor }$, и разложим n по основанию ${\displaystyle m}$:

   ${\displaystyle n=m^{d}+a_{d-1}m^{d-1}+\dots +a_{0}}$ (1)

3. Свяжем с разложением (1) неприводимый в кольце ${\displaystyle \mathbb {Z} [x]}$ полиномов с целыми коэффициентами многочлен

   ${\displaystyle f_{1}(x)=x^{d}+a_{d-1}x^{d-1}+\dots +a_{0}}$

4. Определим полином просеивания ${\displaystyle F_{1}(a,b)}$ как однородный многочлен от двух переменных ${\displaystyle a}$ и ${\displaystyle b}$:

   ${\displaystyle F_{1}(a,b)=b^{d}\cdot f_{1}(a/b)=a^{d}+a_{d-1}a^{d-1}b+a_{d-2}a^{d-2}b^{2}+...+a_{0}b^{d}}$ (2)

5. Определим второй полином ${\displaystyle f_{2}(x)=x-m}$ и соответствующий однородный многочлен ${\displaystyle F_{2}(a,b)=a-bm}$.
6. Выберем два положительных числа ${\displaystyle L_{1}}$ и ${\displaystyle L_{2}}$, определяющих область просеивания (англ. sieve region):

   ${\displaystyle SR=\{1\leq b\leq L_{1},-L_{2}\leq a\leq L_{2}\}}$

7. Пусть ${\displaystyle \theta }$ — корень ${\displaystyle f_{1}(x)}$. Рассмотрим кольцо полиномов ${\displaystyle \mathbb {Z} [\theta ]}$. Определим множество, называемое алгебраической факторной базой ${\displaystyle FB_{1}}$, состоящее из многочленов первого порядка вида ${\displaystyle a-b\theta }$ с нормой (2), являющейся простым числом. Эти многочлены — простые неразложимиые в кольце алгебраических целых поля ${\displaystyle K=\mathbb {Q} [\theta ]}$. Ограничим абсолютные значения норм полиномов из ${\displaystyle FB_{1}}$ константой ${\displaystyle B_{1}}$.
8. Определим рациональную факторную базу ${\displaystyle FB_{2}}$, состоящую из всех простых чисел, ограниченных сверху константой ${\displaystyle B_{2}}$.
9. Определим множество ${\displaystyle FB_{3}}$, называемое факторной базой квадратичных характеров. Это множество полиномов первого порядка ${\displaystyle c-d\theta }$, норма которых - простое число. Должно выполняться условие ${\displaystyle FB_{1}\cap FB_{3}=\emptyset }$.
10. Выполним просеивание многочленов ${\displaystyle \{a-b\theta \mid (a,b)\in SR\}}$ по факторной базе ${\displaystyle FB_{1}}$ и целых чисел ${\displaystyle \{a-bm\mid (a,b)\in SR\}}$ по факторной базе ${\displaystyle FB_{2}}$. В результате получим множество ${\displaystyle M}$, состоящее из гладких пар ${\displaystyle (a,b)}$, то есть таких пар ${\displaystyle (a,b)}$, что НОД(a,b) = 1, полином и число ${\displaystyle a-b\theta }$ и ${\displaystyle a-bm}$ раскладываются полностью по ${\displaystyle FB_{1}}$ и ${\displaystyle FB_{2}}$ соответственно.
11. Найдём такое подмножество ${\displaystyle S\subseteq M}$, что

    ${\displaystyle \prod _{(a,b)\in S}Nr(a-b\theta )=H^{2},H\in \mathbb {Z} ;~~\prod _{(a,b)\in S}(a-bm)=B^{2},B\in \mathbb {Z} }$

12. Определим многочлен

    ${\displaystyle g(\theta )={f_{1}'}^{2}(\theta )\cdot \prod _{(a,b)\in S}(a-b\theta )}$

    где ${\displaystyle f_{1}'(x)}$ — производная ${\displaystyle f_{1}(x)}$
13. Многочлен ${\displaystyle g(\theta )}$ является полным квадратом в кольце полиномов ${\displaystyle \mathbb {Z} (\theta )}$. Пусть тогда ${\displaystyle \alpha (\theta )}$ есть корень из ${\displaystyle g(\theta )}$ и ${\displaystyle B}$ — корень из ${\displaystyle B^{2}}$.
14. Строим отображение ${\displaystyle \phi \colon \theta \to m}$, заменяя полином ${\displaystyle \alpha (\theta )}$ числом ${\displaystyle \alpha (m)}$. Это отображение является кольцевым гомоморфизмом кольца алгебраических целых чисел ${\displaystyle \mathbb {Z} _{K}}$ в кольцо ${\displaystyle \mathbb {Z} }$, откуда получаем соотношение:

    ${\displaystyle A^{2}={g(m)}^{2}\equiv {\phi (g(\alpha ))}^{2}\equiv \phi ({f_{1}'}^{2}(\theta )\cdot \prod _{(a,b)\in S}(a-b\theta ))\equiv {f_{1}'}^{2}(m)\cdot \prod _{(a,b)\in S}(a-bm)\equiv {f_{1}'}^{2}(m)\cdot C^{2}{\pmod {n}}}$

15. Пусть ${\displaystyle B=f'(m)\cdot C}$. Найдём пару чисел ${\displaystyle (A,B)}$ таких, что ${\displaystyle A\equiv B{\pmod {n}}}$. Тогда найдём делитель числа ${\displaystyle n}$, вычисляя НОД(n, A ± B), как это делается, например, в методе квадратичного решета.

Подробное описание алгоритма можно найти, например, в ^[11] и ^[12].

До 2007 года наиболее успешной реализацией считалось программное обеспечение, разработанное и распространяемое Центром математики и информатики (CWI) в Нидерландах, распространявшееся под закрытой лицензией.

В 2007 году Джейсон Пападопулос^[англ.] реализовал часть алгоритма, занимающуюся окончательной обработкой данных, так, что она работала быстрее версии CWI. Этот код входит в библиотеку msieve. Msieve написана Пападопулосом и другими участниками проекта на C и включает в себя реализации общего метода решета числового поля и квадратичного решета. Распространяется на правах общественного достояния. Поддерживает распределенные вычисления. Последняя версия msieve может быть найдена на сайте автора.

Некоторые другие реализации общего метода решета числового поля:

• NFS@Home Архивная копия от 7 декабря 2012 на Wayback Machine - исследовательский проект, направленный на факторизацию больших чисел с помощью общего метода решета числового поля, использующий сеть из подключившихся к проекту компьютеров для просеивания.
• GGNFS Архивная копия от 14 марта 2013 на Wayback Machine, распространяется под GPL.
• pGNFS Архивная копия от 15 февраля 2013 на Wayback Machine
• factor by gnfs Архивная копия от 12 октября 2012 на Wayback Machine
• CADO-NFS Архивная копия от 28 августа 2011 на Wayback Machine
• kmGNFS Архивная копия от 21 октября 2021 на Wayback Machine

В 1996 году с помощью алгоритма было получено разложение числа RSA-130. Позднее с помощью метода были факторизованы, например, числа RSA-140^[13], и RSA-155^[14]. На разложение последнего потребовалось более 8000 mips лет. 9 мая 2005 года Ф. Бар, М. Бом, Йенс Франке и Т. Клейнжунг объявили, что они разложили число RSA-200, используя общий метод решета числового поля.

В 2009 году группе учёных из Швейцарии, Японии, Франции, Нидерландов, Германии и США удалось успешно вычислить данные, зашифрованные при помощи криптографического ключа стандарта RSA длиной 768 битов.^[15] Как следует из описания работы, вычисление значений ключа осуществлялось общим методом решета числового поля. По словам исследователей, после их работы в качестве надежной системы шифрования можно рассматривать только RSA-ключи длиной 1024 бита и более.^[16]

• Специальный метод решета числового поля
• Факторизация целых чисел