Общий метод решета числового поля
Общий метод решета числового поля (англ. general number field sieve, GNFS) — метод факторизации целых чисел. Является наиболее эффективным алгоритмом факторизации чисел длиной более 110 десятичных знаков. Сложность алгоритма оценивается эвристической формулой[1]
- [math]\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] }[/math]
Метод является обобщением специального метода решета числового поля: тогда как последний позволяет факторизовать числа только некоторого специального вида, общий метод работает на множестве целых чисел, за исключением степеней простых чисел (которые факторизуются тривиально извлечением корней).
История
В 1988 году английский математик Джон Поллард описал новый метод факторизации целых чисел специальной формы ([math]\displaystyle{ 2^n \pm C }[/math]), проиллюстрировав его разложением седьмого числа Ферма [math]\displaystyle{ F_7 = 2^{128}+1 }[/math]. В отличие от метода квадратичного решета, в котором просеивание выполняется в кольце всех целых чисел, в методе предлагалось использовать кольцо целых чисел [math]\displaystyle{ Z([2^{3/2}]) }[/math] над числовым полем [math]\displaystyle{ Q(2^{3/2}) }[/math]. Рукопись была приложена к письму, адресованному Эндрю Одлыжко , также копии получили Ричард Брент, Джон Бриллхарт , Хендрик Ленстра, Клаус Шнорр и Х. Суяма. В этом письме Поллард предположил, что возможно этот метод может быть использован для разложения девятого числа Ферма.[2]
В 1990 году А. Ленстра, Х. Ленстра, Марк Манассе и Поллард описали первую крупномасштабную реализацию нового метода с некоторыми усовершенствованиями. Они показали, что на числах специального вида алгоритм работает быстрее, чем все остальные известные методы факторизации. Также в работе обсуждается идея Джо Бухлера и Карла Померанса об усовершенствовании метода для разложения любых целых чисел и приводятся наброски решения этой задачи.[3]
Позднее Леонард Макс Адлеман предложил использовать квадратичный характер для нахождения квадратов в числовом поле. Это предоставило альтернативное решение проблемы, поднятой Бухлером и Померансом, и улучшило предположительное время работы решета числового поля в применении к числам не специального вида.[4]
В том же году А. Ленстра, Х. Ленстра, Манассе и Поллард представили разложение девятого числа Ферма с помощью метода числового поля. В соответствующей работе обсуждаются многие детали этого разложения.[5]
Наконец, в работе «Факторизация целых чисел с помощью решета числового поля» Бухлер, Х. Ленстра и Померанс описали метод решета числового поля в применении к числам, которые не обязательно имеют специальный вид.[6] Эта реализация алгоритма содержала шаг, предполагающий вычисления с использованием чрезвычайно больших чисел. Джин-Марк Кувейгнес в своей работе описал способ обойти это.[7]
Итоги раннего развития метода подвёл сборник статей под редакций А. Ленстры и Х. Ленстры.[8] В том числе сборник включал статью Бернштейна и А. Ленстры, описывающую очередную улучшенную реализацию алгоритма. Статья вошла в сборник под заголовком «Общий метод решета числового поля».[9]
Суть метода
Метод решета числового поля (как специальный, так и общий) можно представить как усовершенствование более простого метода — метода рационального решета либо метода квадратичного решета. Подобные им алгоритмы требуют нахождения гладких чисел порядка [math]\displaystyle{ \sqrt{n} }[/math]. Размер этих чисел экспоненциально растёт с ростом [math]\displaystyle{ n }[/math]. Метод решета числового поля, в свою очередь, требует нахождения гладких чисел субэкспоненциального относительно [math]\displaystyle{ n }[/math] размера. Благодаря тому, что эти числа меньше, вероятность того, что число такого размера окажется гладким, выше, что и является причиной эффективности метода решета числового поля. Для достижения ускорения вычислений в рамках метода проводятся в числовых полях, что усложняет алгоритм, по сравнению с более простым рациональным решетом.
Основные принципы
- Метод факторизации Ферма для факторизации натуральных нечетных чисел n, состоящий в поиске таких целых чисел x и y, что [math]\displaystyle{ x^2-y^2=n }[/math], что ведет к разложению [math]\displaystyle{ n=(x-y)\cdot (x+y) }[/math].
- Нахождение подмножества множества целых чисел, произведение которых — квадрат[10]
- Составление факторной базы: набора [math]\displaystyle{ \{ -1, p_1, p_2, \dots, p_n\} }[/math], где pi — простые числа, такие, что [math]\displaystyle{ p_i \leqslant B }[/math] для некоторого B.
- Просеивание выполняется подобно решету Эратосфена (откуда метод и получил своё название). Решетом служат простые числа факторной базы и их степени. При просеивании число не «вычёркивается», а делится на число из решета. Если в результате число оказалось единицей, то оно B-гладкое.
- Основная идея состоит в том, чтобы вместо перебора чисел и проверки, делятся ли их квадраты по модулю n на простые числа из факторной базы, перебираются простые числа из базы и сразу для всех чисел вида [math]\displaystyle{ x^{2} - n }[/math] проверяется, делятся ли они на это простое число или его степень.
Алгоритм
Пусть [math]\displaystyle{ n }[/math] — нечетное составное число, которое требуется факторизовать.
- Выберем степень неприводимого многочлена [math]\displaystyle{ d \ge 3 }[/math] (при [math]\displaystyle{ d = 2 }[/math] не будет выигрыша в сравнении с методом квадратичного решета).
-
Выберем целое [math]\displaystyle{ m }[/math] такое, что [math]\displaystyle{ \lfloor n^{1/(d+1)} \rfloor \lt m \lt \lfloor n^{1/d} \rfloor }[/math], и разложим n по основанию [math]\displaystyle{ m }[/math]:
- [math]\displaystyle{ n = m^d + a_{d-1}m^{d-1} + \dots + a_0 }[/math] (1)
-
Свяжем с разложением (1) неприводимый в кольце [math]\displaystyle{ \mathbb Z[x] }[/math] полиномов с целыми коэффициентами многочлен
- [math]\displaystyle{ f_1(x) = x^d + a_{d-1}x^{d-1} + \dots + a_0 }[/math]
-
Определим полином просеивания [math]\displaystyle{ F_1(a,b) }[/math] как однородный многочлен от
двух переменных [math]\displaystyle{ a }[/math] и [math]\displaystyle{ b }[/math]:
- [math]\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 }[/math] (2)
- Определим второй полином [math]\displaystyle{ f_2(x) = x - m }[/math] и соответствующий однородный многочлен [math]\displaystyle{ F_2(a,b) = a - bm }[/math].
-
Выберем два положительных числа [math]\displaystyle{ L_1 }[/math] и [math]\displaystyle{ L_2 }[/math], определяющих область просеивания (англ. sieve region):
- [math]\displaystyle{ SR = \{1 \le b \le L_1, -L_2 \le a \le L_2 \} }[/math]
- Пусть [math]\displaystyle{ \theta }[/math] — корень [math]\displaystyle{ f_1(x) }[/math]. Рассмотрим кольцо полиномов [math]\displaystyle{ \mathbb Z[\theta] }[/math]. Определим множество, называемое алгебраической факторной базой [math]\displaystyle{ FB_1 }[/math], состоящее из многочленов первого порядка вида [math]\displaystyle{ a - b \theta }[/math] с нормой (2), являющейся простым числом. Эти многочлены — простые неразложимиые в кольце алгебраических целых поля [math]\displaystyle{ K = \mathbb Q[\theta] }[/math]. Ограничим абсолютные значения норм полиномов из [math]\displaystyle{ FB_1 }[/math] константой [math]\displaystyle{ B_1 }[/math].
- Определим рациональную факторную базу [math]\displaystyle{ FB_2 }[/math], состоящую из всех простых чисел, ограниченных сверху константой [math]\displaystyle{ B_2 }[/math].
- Определим множество [math]\displaystyle{ FB_3 }[/math], называемое факторной базой квадратичных характеров. Это множество полиномов первого порядка [math]\displaystyle{ c - d \theta }[/math], норма которых - простое число. Должно выполняться условие [math]\displaystyle{ FB_1 \cap FB_3 = \empty }[/math].
- Выполним просеивание многочленов [math]\displaystyle{ \{a - b \theta \mid (a,b) \in SR\} }[/math] по факторной базе [math]\displaystyle{ FB_1 }[/math] и целых чисел [math]\displaystyle{ \{a - b m \mid (a,b) \in SR\} }[/math] по факторной базе [math]\displaystyle{ FB_2 }[/math]. В результате получим множество [math]\displaystyle{ M }[/math], состоящее из гладких пар [math]\displaystyle{ (a, b) }[/math], то есть таких пар [math]\displaystyle{ (a, b) }[/math], что НОД(a,b) = 1, полином и число [math]\displaystyle{ a - b \theta }[/math] и [math]\displaystyle{ a - b m }[/math] раскладываются полностью по [math]\displaystyle{ FB_1 }[/math] и [math]\displaystyle{ FB_2 }[/math] соответственно.
-
Найдём такое подмножество [math]\displaystyle{ S \subseteq M }[/math], что
- [math]\displaystyle{ \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 }[/math]
-
Определим многочлен
- [math]\displaystyle{ g(\theta) = {f_1'}^2(\theta) \cdot \prod_{(a,b) \in S} (a - b \theta) }[/math]
- Многочлен [math]\displaystyle{ g(\theta) }[/math] является полным квадратом в кольце полиномов [math]\displaystyle{ \mathbb Z(\theta) }[/math]. Пусть тогда [math]\displaystyle{ \alpha(\theta) }[/math] есть корень из [math]\displaystyle{ g(\theta) }[/math] и [math]\displaystyle{ B }[/math] — корень из [math]\displaystyle{ B^2 }[/math].
-
Строим отображение [math]\displaystyle{ \phi \colon \theta \to m }[/math], заменяя полином [math]\displaystyle{ \alpha(\theta) }[/math] числом [math]\displaystyle{ \alpha(m) }[/math]. Это отображение является кольцевым гомоморфизмом кольца алгебраических целых чисел [math]\displaystyle{ \mathbb Z_K }[/math] в кольцо [math]\displaystyle{ \mathbb Z }[/math], откуда получаем соотношение:
- [math]\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 - b m) \equiv {f_1'}^2(m) \cdot C^2 \pmod n }[/math]
- Пусть [math]\displaystyle{ B = f'(m) \cdot C }[/math]. Найдём пару чисел [math]\displaystyle{ (A, B) }[/math] таких, что [math]\displaystyle{ A \equiv B \pmod n }[/math]. Тогда найдём делитель числа [math]\displaystyle{ n }[/math], вычисляя НОД(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]
См. также
Примечания
- ↑ Pomerance, Carl. A Tale of Two Sieves (англ.) // Notices of the AMS : journal. — 1996. — Vol. 43, no. 12. — P. 1473—1485.
- ↑ J. M. Pollard (1988), Factoring with cubic numbers
- ↑ 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
- ↑ Leonard M. Adleman (1991), Factoring numbers using singular integers, с. 64-71, ISBN 0-89791-397-3
- ↑ 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.
- ↑ 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.
- ↑ Jean-marc Couveignes. Computing A Square Root For The Number Field Sieve (неопр.) // Lecture Notes in Mathematics. — 1993. — Т. 1554. — С. 95—102. — doi:10.1007/BFb0091540.
- ↑ A. K. Lenstra, H. W. Lenstra (1993), The Development of the Number Field Sieve, Springer, ISBN 9783540570134
- ↑ Jean-marc Couveignes. A general number field sieve implementation (неопр.) // Lecture Notes in Mathematics. — 1993. — Т. 1554. — С. 103—126. — doi:10.1007/BFb0091541.
- ↑ И. В. Агафонова Факторизация больших целых чисел и криптография Архивная копия от 26 февраля 2015 на Wayback Machine.
- ↑ Briggs M. (1998), An Introduction to the General Number Field Sieve, <http://www.math.vt.edu/people/brown/doc/briggs_gnfs_thesis.pdf> Архивная копия от 8 августа 2017 на Wayback Machine
- ↑ Ишмухаметов Ш. Т. Методы факторизации натуральных чисел. — Казань: Казан. ун.. — 2011. — 190 с.
- ↑ 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.
- ↑ 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.
- ↑ Анонс факторизации RSA-768 Архивная копия от 13 апреля 2014 на Wayback Machine (англ.)
- ↑ Факториация RSA-768 Архивная копия от 13 декабря 2012 на Wayback Machine (англ.)