Общий метод решета числового поля
Общий метод решета числового поля (англ. general number field sieve, GNFS) — метод факторизации целых чисел. Является наиболее эффективным алгоритмом факторизации чисел длиной более 110 десятичных знаков. Сложность алгоритма оценивается эвристической формулой[1]
Метод является обобщением специального метода решета числового поля: тогда как последний позволяет факторизовать числа только некоторого специального вида, общий метод работает на множестве целых чисел, за исключением степеней простых чисел (которые факторизуются тривиально извлечением корней).
История
[править | править код]В 1988 году английский математик Джон Поллард[англ.] описал новый метод факторизации целых чисел специальной формы (), проиллюстрировав его разложением седьмого числа Ферма . В отличие от метода квадратичного решета, в котором просеивание выполняется в кольце всех целых чисел, в методе предлагалось использовать кольцо целых чисел над числовым полем . Рукопись была приложена к письму, адресованному Эндрю Одлыжко[англ.], также копии получили Ричард Брент, Джон Бриллхарт[англ.], Хендрик Ленстра, Клаус Шнорр[англ.] и Х. Суяма. В этом письме Поллард предположил, что возможно этот метод может быть использован для разложения девятого числа Ферма.[2]
В 1990 году А. Ленстра, Х. Ленстра, Марк Манассе и Поллард описали первую крупномасштабную реализацию нового метода с некоторыми усовершенствованиями. Они показали, что на числах специального вида алгоритм работает быстрее, чем все остальные известные методы факторизации. Также в работе обсуждается идея Джо Бухлера и Карла Померанса об усовершенствовании метода для разложения любых целых чисел и приводятся наброски решения этой задачи.[3]
Позднее Леонард Макс Адлеман предложил использовать квадратичный характер для нахождения квадратов в числовом поле. Это предоставило альтернативное решение проблемы, поднятой Бухлером и Померансом, и улучшило предположительное время работы решета числового поля в применении к числам не специального вида.[4]
В том же году А. Ленстра, Х. Ленстра, Манассе и Поллард представили разложение девятого числа Ферма с помощью метода числового поля. В соответствующей работе обсуждаются многие детали этого разложения.[5]
Наконец, в работе «Факторизация целых чисел с помощью решета числового поля» Бухлер, Х. Ленстра и Померанс описали метод решета числового поля в применении к числам, которые не обязательно имеют специальный вид.[6] Эта реализация алгоритма содержала шаг, предполагающий вычисления с использованием чрезвычайно больших чисел. Джин-Марк Кувейгнес в своей работе описал способ обойти это.[7]
Итоги раннего развития метода подвёл сборник статей под редакций А. Ленстры и Х. Ленстры.[8] В том числе сборник включал статью Бернштейна и А. Ленстры, описывающую очередную улучшенную реализацию алгоритма. Статья вошла в сборник под заголовком «Общий метод решета числового поля».[9]
Суть метода
[править | править код]Метод решета числового поля (как специальный, так и общий) можно представить как усовершенствование более простого метода — метода рационального решета либо метода квадратичного решета. Подобные им алгоритмы требуют нахождения гладких чисел порядка . Размер этих чисел экспоненциально растёт с ростом . Метод решета числового поля, в свою очередь, требует нахождения гладких чисел субэкспоненциального относительно размера. Благодаря тому, что эти числа меньше, вероятность того, что число такого размера окажется гладким, выше, что и является причиной эффективности метода решета числового поля. Для достижения ускорения вычислений в рамках метода проводятся в числовых полях, что усложняет алгоритм, по сравнению с более простым рациональным решетом.
Основные принципы
[править | править код]- Метод факторизации Ферма для факторизации натуральных нечетных чисел n, состоящий в поиске таких целых чисел x и y, что , что ведет к разложению .
- Нахождение подмножества множества целых чисел, произведение которых — квадрат[10]
- Составление факторной базы: набора , где pi — простые числа, такие, что для некоторого B.
- Просеивание выполняется подобно решету Эратосфена (откуда метод и получил своё название). Решетом служат простые числа факторной базы и их степени. При просеивании число не «вычёркивается», а делится на число из решета. Если в результате число оказалось единицей, то оно B-гладкое.
- Основная идея состоит в том, чтобы вместо перебора чисел и проверки, делятся ли их квадраты по модулю n на простые числа из факторной базы, перебираются простые числа из базы и сразу для всех чисел вида проверяется, делятся ли они на это простое число или его степень.
Алгоритм
[править | править код]Пусть — нечетное составное число, которое требуется факторизовать.
- Выберем степень неприводимого многочлена (при не будет выигрыша в сравнении с методом квадратичного решета).
-
Выберем целое такое, что , и разложим n по основанию :
- (1)
-
Свяжем с разложением (1) неприводимый в кольце полиномов с целыми коэффициентами многочлен
-
Определим полином просеивания как однородный многочлен от
двух переменных и :
- (2)
- Определим второй полином и соответствующий однородный многочлен .
-
Выберем два положительных числа и , определяющих область просеивания (англ. sieve region):
- Пусть — корень . Рассмотрим кольцо полиномов . Определим множество, называемое алгебраической факторной базой , состоящее из многочленов первого порядка вида с нормой (2), являющейся простым числом. Эти многочлены — простые неразложимиые в кольце алгебраических целых поля . Ограничим абсолютные значения норм полиномов из константой .
- Определим рациональную факторную базу , состоящую из всех простых чисел, ограниченных сверху константой .
- Определим множество , называемое факторной базой квадратичных характеров. Это множество полиномов первого порядка , норма которых - простое число. Должно выполняться условие .
- Выполним просеивание многочленов по факторной базе и целых чисел по факторной базе . В результате получим множество , состоящее из гладких пар , то есть таких пар , что НОД(a,b) = 1, полином и число и раскладываются полностью по и соответственно.
-
Найдём такое подмножество , что
-
Определим многочлен
- Многочлен является полным квадратом в кольце полиномов . Пусть тогда есть корень из и — корень из .
-
Строим отображение , заменяя полином числом . Это отображение является кольцевым гомоморфизмом кольца алгебраических целых чисел в кольцо , откуда получаем соотношение:
- Пусть . Найдём пару чисел таких, что . Тогда найдём делитель числа , вычисляя НОД(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. Архивировано 11 ноября 2020 года.
- ↑ 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, pp. 564–572, ISBN 0-89791-361-2
{{citation}}
: Википедия:Обслуживание CS1 (множественные имена: authors list) (ссылка) - ↑ Leonard M. Adleman (1991), Factoring numbers using singular integers, pp. 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 (PDF), Архивировано из оригинала (PDF) 8 августа 2017, Дата обращения: 30 ноября 2012
- ↑ Ишмухаметов Ш. Т. Методы факторизации натуральных чисел. — Казань: Казан. ун.. — 2011. — 190 с. Архивировано 26 ноября 2019 года.
- ↑ 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 (англ.)