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

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

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

Суть метода

Метод числового поля (как специальный, так и общий) можно представить как усовершенствование более простого метода — метода рационального решета, либо метода квадратичного решета. Подобные им алгоритмы требуют нахождение гладких чисел порядка n^{1/2}. Размер этих чисел экспоненциально растёт с ростом 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} + ... + a_0 (1)
  3. Свяжем с разложением (1) неприводимый в кольце  \mathbb Z[x] полиномов с целыми коэффициентами многочлен
     f_1(x) = x^d + a_{d-1}x^{d-1} + ... + 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, cостоящее из многочленов первого порядка вида  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 года наиболее успешной реализацией считалось программное обеспечение разработанное и распространяемое Центром математики и информатики в Нидерландах, распространявшееся под закрытой лицензией.

В 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 (December 1996), "«A Tale of Two Sieves»", Notices of the AMS Т. 43 (12): 1473–1485, <http://www.ams.org/notices/199612/pomerance.pdf> 
  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», сс. 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  (англ.)

Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Полезное


Смотреть что такое "Общий метод решета числового поля" в других словарях:

  • Специальный метод решета числового поля — (англ. special number field sieve, SNFS) является методом факторизации целых чисел особого вида. Из него был получен общий метод решета числового поля, являющийся наиболее эффективным алогритмом факторизации больших целых чисел . Метод… …   Википедия

  • Метод квадратичного решета — (Quadratic sieve algorithm, сокр. QS)  метод факторизации больших чисел, разработанный Померанцем в 1981 году. Долгое время превосходил другие методы факторизации целых чисел общего вида, не имеющих простых делителей, порядок которых… …   Википедия

  • RSA-числа — это множество больших полупростых чисел (чисел, представимых в виде произведения двух простых чисел), используемых в конкурсе RSA Factoring Challenge. Конкурс заключался в нахождении простых множителей предложенных чисел, но в 2007 году был… …   Википедия

  • Факторизация целых чисел — Факторизацией натурального числа называется его разложение в произведение простых множителей. Существование и единственность (с точностью до порядка следования множителей) такого разложения следует из основной теоремы арифметики. В отличие от… …   Википедия

  • Разложение на множители — Факторизация разложение данного натурального числа на простые множители. В отличие от задачи распознавания простоты числа, факторизация предположительно является сложной задачей. Содержание 1 Алгоритмы факторизации 1.1 Экспоненциальные алгоритмы …   Википедия

  • RSA — (аббревиатура от фамилий Rivest, Shamir и Adleman)  криптографический алгоритм с открытым ключом, основывающийся на вычислительной сложности задачи факторизации больших целых чисел. Криптосистема RSA стала первой системой, пригодной и для… …   Википедия

  • Ρ-алгоритм Полларда — Эта статья  о факторизации чисел. О методе дискретного логарифмирования см. Ρ метод Полларда дискретного логарифмирования. Числовая последовательность зацикливается, начиная с неко …   Википедия

  • Факторизация с помощью эллиптических кривых — (англ. elliptic curve method, сокр. ECM)  алгоритм факторизации натурального числа с использованием эллиптических кривых. Данный алгоритм имеет субэкспоненциальное время выполнения. Является третьим по скорости работы после общего… …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»