Специальный метод решета числового поля

Специальный метод решета числового поля (англ. special number field sieve, SNFS) является методом факторизации целых чисел особого вида. Из него был получен общий метод решета числового поля, являющийся наиболее эффективным алогритмом факторизации больших целых чисел $n > 10^{110}$. Метод эффективен для целых чисел вида r^e ± s, где r $\in$ N s $\in$ Z, r и s невелики(например Числа Мерсенна).

Эвристическая оценка сложности факторизации числа n выражается формулой^[1]:

$e^{\left(1+o(1)\right)\left(\frac{32}{9}\log n\right)^{\frac{1}{3}}\left(\log\log n\right)^{\frac{2}{3}}}=L_n\left[1/3,(32/9)^{1/3}\right]$

С помощью SNFS было разложено на множители число Ферма $F_9 = 2^{512}+1$, содержащее 155 десятичных цифр^[2].

История возникновения

Основную идею метода впервые предложил Джон Поллард (англ.) в своей статье^[3], которую он разослал своим коллегам в 1988 г. В ней он проиллюстрировал свой метод на седьмом числе Ферма $2^{128}+1$. Идея заключалась в выполнении просеивания не в кольце целых чисел, как в методе квадратичного решета, а в алгебраическом числовом поле. В 1990 году с помощью этого метода было разложено девятое число Ферма $F9 = 2^{512}+1$. Изначально метод был применим только для чисел специального вида 2ⁿ ± c, поэтому и получил название «специальный метод решета числового поля». Позже метод был модифицирован для произвольных чисел и назван общим методом числового решета.

Обзор метода

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

• Нахождение числа мультипликативных соотношений факторной базы Z/nZ, большего чем число элементов в факторной базе.
• Перемножение соотношений между собой таким образом, чтобы степени полученных произведений были одинаковыми, то есть получение соотношений вида a²≡b² (mod n). Это в свою очередь приведет к факторизации n: n=НОД(a+b,n)×НОД(a-b,n). В случае, если полученное разложение является тривиальным (то есть n=n×1), следует искать другие произведения соотношений, удовлетворяющие данному условию.

Второй шаг идентичен шагу в методе рационального решета и является задачей линейной алгебры. В отличие от первого шага, который в этом методе является более эффективным.

Детали метода

Пусть n — это факторизуемое число. Возьмем неприводимый многочлен f и целое число m, такое что f(m)≡0 (mod n) (принципы их выбора будут объяснены в следующем разделе). Пусть α корень f; тогда существует кольцо Z[α]. Тогда существует единственное кольцо гомоморфизма (англ.) φ между Z[α] и Z/nZ, которое отображает α в m. Для простоты полагаем, что Z[α] является факториальным кольцом; метод может быть модифицирован для случая, когда это условие не выполняется, что приведет к дополнительным вычислениям.

Затем создадим две факторных базы, одну для Z[α] и одну для Z. Факторная база Z[α] содержит все простые числа Z[α], чей размер ограничен значением $N_{\max}$. Факторная база Z, как и в методе рационального решета, состоит из простых чисел до некоторого граничного числа.

Затем ищем такие взаимно простые числа (a,b) что:

• a+bm является гладким по отношению к элементам факторной базы Z (то есть все его простые делители содержатся в факторной базе).
• a+bα является гладким по отношению к элементам факторной базы Z[α];из того как мы выбирали элементы факторной базы, это условие эквивалентно тому, что a+bα делится только на простые числа, меньшие $N_{\max}$.

Эти пары чисел находятся методом просеивания, аналогичным методу решета Эратосфена; это объясняет название метода решета числового поля.

Для каждой такой пары чисел (a,b) мы можем применить кольцо гомоморфизма φ для факторизации a+bα и каноническое кольцо гомоморфизма от Z до Z/nZ для факторизации a+bm. Приравняв их, получим мультипликативные соотношения для элементов факторной базы Z/nZ. Найдя достаточное количество таких соотношений, перемножаем их между собой как описано выше.

Выбор параметров

Не каждое число подходит для факторизации методом SNFS: необходимо заранее найти полином f подходящей степени (оптимальная степень полагается равной $\left(3 \frac{\log N}{\log \log N}\right) ^{1/3}$; для факторизуемых на данных момент чисел N это 4,5 или 6) с малыми коэффициентами и такое x, что $f(x) \equiv 0 \pmod N$, где N число для факторизации. Также x должен быть таким, чтобы выполнялось $ax+b \equiv 0 \pmod N$ для a и b не больших $N^{1/d}$.

Одним из видов чисел, для которых такие полиномы существуют являются числа вида $a^b \pm 1$; например, когда NFSNET раскладывали число 3^479+1, они использовали полином x^6+3 при x=3^80, так как (3^80)^6+3 = 3^480+3 и $3^{480}+3 \equiv 0 \pmod {3^{479}+1}$.

У чисел, определяемых линейными рекуррентными соотношениями, таких как числа Фибоначчи и числа Люка, тоже есть полиномы SNFS, но их немного сложнее получить. Например, $F_{709}$ имеет полином $n^5 + 10n^3 + 10n^2 + 10n + 3$, и значение x, удовлетворяющее $F_{142} x - F_{141} = 0$.^[4]

Если вам известны некоторые делители большого SNFS-числа, вы можете произвести SNFS вычисления для оставшейся части; для примера выше от NFSNET, 3^479+1 = (4·158071·7167757·7759574882776161031) раз 197-знаковое составное число (небольших делители были исключены методом ECM), и SNFS применялся для 197-значного числа. Число операций для NFS зависит от размера исходного числа, но некоторые вычисления производятся быстрее по модулю меньшего числа.

Ограничения

Этот метод, как подмечено выше, очень эффективен для чисел вида r^e±s, где r и s относительно маленькие. Он также эффективен для чисел, представимых в виде полинома с небольшими коэффициентами. Дело в том, что специальный метод решета числового поля производит просеивание для двух числовых полей. Эффективность метода сильно зависит от размера определенных элементов в этих полях. Если число можно представить в виде полинома с маленькими коэффициентами, числа, с которыми производятся вычисления, намного меньше чисел, с которыми приходится иметь дело, если такого полинома не существует.

См. также

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

Примечания

1. ↑ Бёме Р. Л., Флинт В. Е. Пятиязычный словарь названий животных. Птицы. Латинский, русский, английский, немецкий, французский. / под общей редакцией акад. В. Е. Соколова. — М.: Рус. яз., «РУССО», 1994. — 845 с. — 2030 экз. — ISBN 5-200-00643-0Pomerance, 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. ↑ Бёме Р. Л., Флинт В. Е. Пятиязычный словарь названий животных. Птицы. Латинский, русский, английский, немецкий, французский. / под общей редакцией акад. В. Е. Соколова. — М.: Рус. яз., «РУССО», 1994. — 845 с. — 2030 экз. — ISBN 5-200-00643-0Василенко, О.Н. (2003), «Теоретико-числовые алгоритмы криптографии», сс. 93-107, <http://www.ict.edu.ru/ft/002416/book.pdf> 
3. ↑ Бёме Р. Л., Флинт В. Е. Пятиязычный словарь названий животных. Птицы. Латинский, русский, английский, немецкий, французский. / под общей редакцией акад. В. Е. Соколова. — М.: Рус. яз., «РУССО», 1994. — 845 с. — 2030 экз. — ISBN 5-200-00643-0Pollard, J.M. (1988), «Factoring with cubic numbers» 
4. ↑ Franke, Jens Installation notes for ggnfs-lasieve4. MIT Massachusetts Institute of Technology. Архивировано из первоисточника 5 сентября 2012.

Литература

• Бёме Р. Л., Флинт В. Е. Пятиязычный словарь названий животных. Птицы. Латинский, русский, английский, немецкий, французский. / под общей редакцией акад. В. Е. Соколова. — М.: Рус. яз., «РУССО», 1994. — 845 с. — 2030 экз. — ISBN 5-200-00643-0Ишмухаметов, Ш.Т. (2011), «Методы факторизации натуральных чисел», сс. 145-175, <http://window.edu.ru/window_catalog/files/r73980/Monograph_ishm.pdf> 
• Бёме Р. Л., Флинт В. Е. Пятиязычный словарь названий животных. Птицы. Латинский, русский, английский, немецкий, французский. / под общей редакцией акад. В. Е. Соколова. — М.: Рус. яз., «РУССО», 1994. — 845 с. — 2030 экз. — ISBN 5-200-00643-0Byrnes, Steven (May 18, 2005), "«The Number Field Sieve»", Math 129, <http://modular.fas.harvard.edu/129-05/final_papers/Steve_Byrnes.pdf> 
• Бёме Р. Л., Флинт В. Е. Пятиязычный словарь названий животных. Птицы. Латинский, русский, английский, немецкий, французский. / под общей редакцией акад. В. Е. Соколова. — М.: Рус. яз., «РУССО», 1994. — 845 с. — 2030 экз. — ISBN 5-200-00643-0Lenstra, A. K.; Lenstra, H. W., Jr.; Manasse, M. S. & Pollard, J. M. (1993), "«The Factorization of the Ninth Fermat Number»", Mathematics of Computation Т. 61 (203): 319–349, doi:10.1090/S0025-5718-1993-1182953-4, <http://www.std.org/~msm/common/f9paper.ps> 
• Бёме Р. Л., Флинт В. Е. Пятиязычный словарь названий животных. Птицы. Латинский, русский, английский, немецкий, французский. / под общей редакцией акад. В. Е. Соколова. — М.: Рус. яз., «РУССО», 1994. — 845 с. — 2030 экз. — ISBN 5-200-00643-0Lenstra, A. K. & Lenstra, H. W., Jr., eds. (1993), «The Development of the Number Field Sieve», vol. 1554, Lecture Notes in Mathematics, New York: Springer-Verlag, ISBN 3540570136 
• Бёме Р. Л., Флинт В. Е. Пятиязычный словарь названий животных. Птицы. Латинский, русский, английский, немецкий, французский. / под общей редакцией акад. В. Е. Соколова. — М.: Рус. яз., «РУССО», 1994. — 845 с. — 2030 экз. — ISBN 5-200-00643-0Silverman, Robert D. (2007), "«Optimal Parameterization of SNFS»", J. Mathematical Cryptology (de Gruyter) . — Т. 1: 105–124 

Ссылки

• NFS@Home