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

Общий метод решета числового поля (англ. 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}$ — нечетное составное число, которое требуется факторизовать.

Выберем степень неприводимого многочлена ${\displaystyle d\geq 3}$ (при ${\displaystyle d=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)

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

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

Определим полином просеивания ${\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)

Определим второй полином ${\displaystyle f_{2}(x)=x-m}$ и соответствующий однородный многочлен ${\displaystyle F_{2}(a,b)=a-bm}$.

Выберем два положительных числа ${\displaystyle L_{1}}$ и ${\displaystyle L_{2}}$, определяющих область просеивания (англ. sieve region):

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

Пусть ${\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}}$.

Определим рациональную факторную базу ${\displaystyle FB_{2}}$, состоящую из всех простых чисел, ограниченных сверху константой ${\displaystyle B_{2}}$.

Определим множество ${\displaystyle FB_{3}}$, называемое факторной базой квадратичных характеров. Это множество полиномов первого порядка ${\displaystyle c-d\theta }$, норма которых - простое число. Должно выполняться условие ${\displaystyle FB_{1}\cap FB_{3}=\emptyset }$.

Выполним просеивание многочленов ${\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}}$ соответственно.

Найдём такое подмножество ${\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} }

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

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

где ${\displaystyle f_{1}'(x)}$ — производная ${\displaystyle f_{1}(x)}$

Многочлен ${\displaystyle g(\theta )}$ является полным квадратом в кольце полиномов ${\displaystyle \mathbb {Z} (\theta )}$. Пусть тогда ${\displaystyle \alpha (\theta )}$ есть корень из ${\displaystyle g(\theta )}$ и ${\displaystyle B}$ — корень из ${\displaystyle B^{2}}$.

Строим отображение ${\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}}}$

Пусть ${\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]

См. также

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

Примечания

1. Pomerance, Carl. A Tale of Two Sieves (англ.) // Notices of the AMS : journal. — 1996. — Vol. 43, no. 12. — P. 1473—1485. Архивировано 11 ноября 2020 года.
2. J. M. Pollard (1988), Factoring with cubic numbers
3. A.K. Lenstra, H.W. Lenstra, Jr., M.S. Manasse, J.M. Pollard (1990), The number field sieve, pp. 564–572, ISBN 0-89791-361-2{{citation}}: Википедия:Обслуживание CS1 (множественные имена: authors list) (ссылка)
4. Leonard M. Adleman (1991), Factoring numbers using singular integers, pp. 64–71, ISBN 0-89791-397-3
5. A.K. Lenstra, H.W. Lenstra, Jr., M.S. Manasse, J.M. Pollard. The Factorization of the Ninth Fermat Number (англ.) // Math. Comp.^[англ.] : journal. — 1993. — Vol. 61. — P. 319—349. — doi:10.1090/S0025-5718-1993-1182953-4.
6. J.P. Buhler, H.W. Lenstra, Carl Pomerance. Factoring integers with the number field sieve (неопр.) // Lecture Notes in Mathematics. — 1993. — Т. 1554. — С. 50—94. — doi:10.1007/BFb0091539.
7. Jean-marc Couveignes. Computing A Square Root For The Number Field Sieve (неопр.) // Lecture Notes in Mathematics. — 1993. — Т. 1554. — С. 95—102. — doi:10.1007/BFb0091540.
8. A. K. Lenstra, H. W. Lenstra (1993), The Development of the Number Field Sieve, Springer, ISBN 9783540570134
9. Jean-marc Couveignes. A general number field sieve implementation (неопр.) // Lecture Notes in Mathematics. — 1993. — Т. 1554. — С. 103—126. — doi:10.1007/BFb0091541.
10. И. В. Агафонова Факторизация больших целых чисел и криптография Архивная копия от 26 февраля 2015 на Wayback Machine.
11. Briggs M. (1998), An Introduction to the General Number Field Sieve (PDF), Архивировано из оригинала (PDF) 8 августа 2017, Дата обращения: 30 ноября 2012 {{citation}}: |archive-date= / |archive-url= несоответствие временной метки; предлагается 8 августа 2017 (справка)
12. Ишмухаметов Ш. Т. Методы факторизации натуральных чисел. — Казань: Казан. ун.. — 2011. — 190 с. Архивировано 26 ноября 2019 года.
13. Cavallar S., Dodson B., Lenstra A. K., Leyland P. C., Lioen W. M., Montgomery P. L., Murphy B., te Riele H. J. J., Zimmerman P. Factorization of RSA-140 using the number field sieve / CWI Report MAS-R9925, September 1999.
14. Cavallar S., Lioen W. M., te Riele H. J. J., Dodson B., Lenstra A. K., Montgomery P. L., Murphy B. et al. Factorization of 512-bit RSA-modulus / CWI Report MAS-R0007, February 2000.
15. Анонс факторизации RSA-768 Архивная копия от 13 апреля 2014 на Wayback Machine  (англ.)
16. Факториация RSA-768 Архивная копия от 13 декабря 2012 на Wayback Machine  (англ.)