- Общий метод решета числового поля
-
Общий метод решета числового поля (англ. 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):
- Пусть — корень . Рассмотрим кольцо полиномов . Определим множество, называемое алгебраической факторной базой , cостоящее из многочленов первого порядка вида с нормой (2), являющейся простым числом. Эти многочлены — простые неразложимиые в кольце алгебраических целых поля . Ограничим абсолютные значения норм полиномов из константой .
- Определим рациональную факторную базу , состоящую из всех простых чисел, ограниченных сверху константой .
- Определим множество , называемое факторной базой квадратичных характеров. Это множество полиномов первого порядка , норма которых - простое число. Должно выполняться условие .
- Выполним просеивание многочленов по факторной базе и целых чисел по факторной базе . В результате получим множество , состоящее из гладких пар , то есть таких пар , что НОД(a,b) = 1, полином и число и раскладываются полностью по и соответственно.
- Найдём такое подмножество , что
- Определим многочлен
- Многочлен является полным квадратом в кольце полиномов . Пусть тогда есть корень из и — корень из .
- Строим отображение , заменяя полином числом . Это отображение является кольцевым гомоморфизмом кольца алгебраических целых чисел в кольцо , откуда получаем соотношение:
- Пусть . Найдём пару чисел таких, что . Тогда найдём делитель числа , вычисляя НОД(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]
См. также
Специальный метод решета числового поля
Примечания
- ↑ 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>
- ↑ 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 (1993), "«The Factorization of the Ninth Fermat Number»", Math. Comp. Т. 61: 319-349, DOI 10.1090/S0025-5718-1993-1182953-4
- ↑ 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
- ↑ Jean-marc Couveignes (1993), "«Computing A Square Root For The Number Field Sieve»", Lecture Notes in Mathematics Т. 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 (1993), «A general number field sieve implementation», сс. 103-126, DOI 10.1007/BFb0091541
- ↑ И. В. Агафонова Факторизация больших целых чисел и криптография.
- ↑ Briggs M. (1998), «An Introduction to the General Number Field Sieve», <http://www.math.vt.edu/people/brown/doc/briggs_gnfs_thesis.pdf>
- ↑ Ишмухаметов, Ш.Т. (2011), «Методы факторизации натуральных чисел», <http://window.edu.ru/window_catalog/files/r73980/Monograph_ishm.pdf>
- ↑ 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 (англ.)
- ↑ Факториация RSA-768 (англ.)
Категория:- Алгоритмы факторизации
Wikimedia Foundation. 2010.