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

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

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

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

С помощью SNFS было разложено на множители число Ферма , содержащее 155 десятичных цифр[2].

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

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

Обзор метода[править | править код]

SNFS основан на более простом методе рационального решета. Читателю предлагается ознакомиться с данным методом до изучения SNFS.

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

  • Нахождение числа мультипликативных соотношений факторной базы Z/nZ, большего чем число элементов в факторной базе.
  • Перемножение соотношений между собой таким образом, чтобы степени полученных произведений были одинаковыми, то есть получение соотношений вида a2b2 (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[α], чей размер ограничен значением . Факторная база Z, как и в методе рационального решета, состоит из простых чисел до некоторого граничного числа.

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

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

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

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

Выбор параметров[править | править код]

Не каждое число подходит для факторизации методом SNFS: необходимо заранее найти полином f подходящей степени (оптимальная степень полагается равной ; для факторизуемых на данных момент чисел N это 4,5 или 6) с малыми коэффициентами и такое x, что , где N число для факторизации. Также x должен быть таким, чтобы выполнялось для a и b не больших .

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

У чисел, определяемых линейными рекуррентными соотношениями, таких как числа Фибоначчи и числа Люка, тоже есть полиномы SNFS, но их немного сложнее получить. Например, имеет полином , и значение x, удовлетворяющее .[4]

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

Ограничения[править | править код]

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

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

Примечания[править | править код]

  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. Василенко, О.Н. (2003), Теоретико-числовые алгоритмы криптографии, с. 93—107, <http://www.ict.edu.ru/ft/002416/book.pdf>  Архивная копия от 27 января 2007 на Wayback Machine
  3. Pollard, J.M. (1988), Factoring with cubic numbers 
  4. Franke, Jens Installation notes for ggnfs-lasieve4. MIT Massachusetts Institute of Technology. Архивировано 5 сентября 2012 года.

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

Ссылки[править | править код]