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

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

Общий метод решета числового поля (англ. 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]

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

Метод решета числового поля (как специальный, так и общий) можно представить как усовершенствование более простого метода — метода рационального решета, либо метода квадратичного решета. Подобные им алгоритмы требуют нахождение гладких чисел порядка \sqrt{n}. Размер этих чисел экспоненциально растёт с ростом 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\}, где pi — простые числа такие, что 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} + \dots + a_0 (1)
  3. Свяжем с разложением (1) неприводимый в кольце  \mathbb Z[x] полиномов с целыми коэффициентами многочлен
     f_1(x) = x^d + a_{d-1}x^{d-1} + \dots + 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, состоящее из многочленов первого порядка вида  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 года наиболее успешной реализацией считалось программное обеспечение разработанное и распространяемое Центром математики и информатики (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 (1996). «A Tale of Two Sieves» (PDF). Notices of the AMS 43 (12): 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 (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». Lecture Notes in Mathematics 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  (англ.)