WikiSort.ru - Не сортированное

Общий метод решета числового поля (англ. 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})}$ . Рукопись была приложена к письму, адресованному Эндрю Одлыжко^[en], также копии получили Ричард Брент, Джон Бриллхарт^[en], Хендрик Ленстра, Клаус Шнорр^[en] и Х. Суяма. В этом письме Поллард предположил, что возможно этот метод может быть использован для разложения девятого числа Ферма.^[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-1}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]

См. также

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

Примечания