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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

Метод является обобщением специального метода решета числового поля: тогда как последний позволяет факторизовать числа только некоторого специального вида, общий метод работает на множестве целых чисел, за исключением степеней простых чисел (которые факторизуются тривиально извлечением корней).

История[править | править код]

В 1988 году английский математик Джон Поллард (англ.) описал новый метод факторизации целых чисел специальной формы (), проиллюстрировав его разложением седьмого числа Ферма . В отличие от метода квадратичного решета, в котором просеивание выполняется в кольце всех целых чисел, в методе предлагалось использовать кольцо целых чисел над числовым полем . Рукопись была приложена к письму, адресованному Эндрю Одлыжко[en], также копии получили Ричард Брент, Джон Бриллхарт[en], Хендрик Ленстра, Клаус Шнорр[en] и Х. Суяма. В этом письме Поллард предположил, что возможно этот метод может быть использован для разложения девятого числа Ферма.[2]

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

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

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

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

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

Суть метода[править | править код]

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

Основные принципы[править | править код]

  • Метод факторизации Ферма для факторизации натуральных нечетных чисел n, состоящий в поиске таких целых чисел x и y, что , что ведет к разложению .
  • Нахождение подмножества множества целых чисел, произведение которых — квадрат[10]
  • Составление факторной базы: набора , где pi — простые числа такие, что для некоторого B.
  • Просеивание выполняется подобно решету Эратосфена (откуда метод и получил своё название). Решетом служат простые числа факторной базы и их степени. При просеивании число не «вычёркивается», а делится на число из решета. Если в результате число оказалось единицей, то оно B-гладкое.
  • Основная идея состоит в том, чтобы вместо перебора чисел и проверки, делятся ли их квадраты по модулю n на простые числа из факторной базы, перебираются простые числа из базы и сразу для всех чисел вида проверяется, делятся ли они на это простое число или его степень.

Алгоритм[править | править код]

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

  1. Выберем степень неприводимого многочлена (при не будет выигрыша в сравнении с методом квадратичного решета).
  2. Выберем целое такое, что , и разложим n по основанию :
    (1)
  3. Свяжем с разложением (1) неприводимый в кольце полиномов с целыми коэффициентами многочлен
  4. Определим полином просеивания как однородный многочлен от двух переменных и :
    (2)
  5. Определим второй полином и соответствующий однородный многочлен .
  6. Выберем два положительных числа и , определяющих область просеивания (англ. sieve region):
  7. Пусть — корень . Рассмотрим кольцо полиномов . Определим множество, называемое алгебраической факторной базой , состоящее из многочленов первого порядка вида с нормой (2), являющейся простым числом. Эти многочлены — простые неразложимиые в кольце алгебраических целых поля . Ограничим абсолютные значения норм полиномов из константой .
  8. Определим рациональную факторную базу , состоящую из всех простых чисел, ограниченных сверху константой .
  9. Определим множество , называемое факторной базой квадратичных характеров. Это множество полиномов первого порядка , норма которых - простое число. Должно выполняться условие .
  10. Выполним просеивание многочленов по факторной базе и целых чисел по факторной базе . В результате получим множество , состоящее из гладких пар , то есть таких пар , что НОД(a,b) = 1, полином и число и раскладываются полностью по и соответственно.
  11. Найдём такое подмножество , что
  12. Определим многочлен
    где — производная
  13. Многочлен является полным квадратом в кольце полиномов . Пусть тогда есть корень из и — корень из .
  14. Строим отображение , заменяя полином числом . Это отображение является кольцевым гомоморфизмом кольца алгебраических целых чисел в кольцо , откуда получаем соотношение:
  15. Пусть . Найдём пару чисел таких, что . Тогда найдём делитель числа , вычисляя НОД(n, A ± B), как это делается, например, в методе квадратичного решета.

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

Реализации[править | править код]

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

В 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. A Tale of Two Sieves (англ.) // Notices of the AMS : journal. — 1996. — Vol. 43, no. 12. — P. 1473—1485.
  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. 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. И. В. Агафонова Факторизация больших целых чисел и криптография.
  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  (англ.)