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

В 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}$ размера. Благодаря тому, что эти числа меньше, вероятность того, что число такого размера окажется гладким, выше, что и является причиной эффективности метода решета числового поля. Для достижения ускорения вычислений в рамках метода проводятся в числовых полях, что усложняет алгоритм, по сравнению с более простым рациональным решетом.

Пусть ${\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 - исследовательский проект, направленный на факторизацию больших чисел с помощью общего метода решета числового поля, использующий сеть из подключившихся к проекту компьютеров для просеивания.
• GGNFS, распространяется под GPL.
• pGNFS
• factor by gnfs
• CADO-NFS
• kmGNFS

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

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

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