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

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

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

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

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

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

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

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

Суть метода

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

Основные принципы, лежащие в основе алгоритма

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

Алгоритм

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

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

   $n = m^d + a_{d-1}m^{d-1} + ... + a_0$ (1)

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

   $f_1(x) = x^d + a_{d-1}x^{d-1} + ... + a_0$

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

   $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. Определим второй полином $f_2(x) = x - m$ и соответствующий однородный многочлен $F_2(a,b) = a - bm$.
6. Выберем два положительных числа $L_1$ и $L_2$, определяющих область просеивания (англ. sieve region):

   $SR = \{1 \le b \le L_1, -L_2 \le a \le L_2 \}$

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

    $\prod_{(a,b) \in S} Nr(a - b\theta) = H^2 , H \in \mathbb Z ; ~~ \prod_{(a,b) \in S} (a - b m) = B^2 , B \in \mathbb Z$

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

    $g(\theta) = {f_1'}^2(\theta) \cdot \prod_{(a,b) \in S} (a - b \theta)$

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

    $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 - b m) \equiv {f_1'}^2(m) \cdot C^2 \pmod n$

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

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

Реализации

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

В 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]

См. также

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

Факторизация целых чисел

Примечания

1. ↑ Pomerance, Carl (December 1996), "«A Tale of Two Sieves»", Notices of the AMS Т. 43 (12): 1473–1485, <http://www.ams.org/notices/199612/pomerance.pdf> 
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», сс. 564-572, ISBN 0-89791-361-2 
4. ↑ Leonard M. Adleman (1991), «Factoring numbers using singular integers», сс. 64-71, ISBN 0-89791-397-3 
5. ↑ A.K. Lenstra, H.W. Lenstra, Jr., M.S. Manasse, J.M. Pollard (1993), "«The Factorization of the Ninth Fermat Number»", Math. Comp. Т. 61: 319-349, DOI 10.1090/S0025-5718-1993-1182953-4 
6. ↑ J.P. Buhler, H.W. Lenstra, Carl Pomerance (1993), "«Factoring integers with the number field sieve»", Lecture Notes in Mathematics Т. 1554: 50-94, DOI 10.1007/BFb0091539 
7. ↑ Jean-marc Couveignes (1993), "«Computing A Square Root For The Number Field Sieve»", Lecture Notes in Mathematics Т. 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 (1993), «A general number field sieve implementation», сс. 103-126, DOI 10.1007/BFb0091541 
10. ↑ И. В. Агафонова Факторизация больших целых чисел и криптография.
11. ↑ Briggs M. (1998), «An Introduction to the General Number Field Sieve», <http://www.math.vt.edu/people/brown/doc/briggs_gnfs_thesis.pdf> 
12. ↑ Ишмухаметов, Ш.Т. (2011), «Методы факторизации натуральных чисел», <http://window.edu.ru/window_catalog/files/r73980/Monograph_ishm.pdf> 
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  (англ.)
16. ↑ Факториация RSA-768  (англ.)