Processing math: 100%

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

Специальный метод решета числового поля (, SNFS) являетсяметодом факторизации целых чисел особого вида. Из него был получен общийметод решета числового поля, являющийся наиболее эффективным алогритмомфакторизации больших целых чисел n>10110. Метод эффективен дляцелых чисел вида re ± s, где r N s Z, r и s невелики(например Числа Мерсенна).
 Эвристическая оценка сложности факторизации числа n выражаетсяформулой:
e(1+o(1))(329logn)13(loglogn)23=Ln[1/3,(32/9)1/3]
 С помощью SNFS было разложено на множители число ФермаF9=2512+1, содержащее 155 десятичных цифр.

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


 Основную идею метода впервые предложил в своей статье, которую онразослал своим коллегам в 1988 г. В ней он проиллюстрировал свой методна седьмом числе Ферма 2128+1. Идея заключалась в выполнениипросеивания не в кольце целых чисел, как в методе квадратичного решета,а в алгебраическом числовом поле. В 1990 году с помощью этого методабыло разложено девятое число Ферма F9=2512+1. Изначально методбыл применим только для чисел специального вида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[α], чей размер ограничен значением Nmax.Факторная база Z, как и в методе рационального решета, состоитиз простых чисел до некоторого граничного числа.
 Затем ищем такие взаимно простые числа (a,b) что:

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

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

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


 Не каждое число подходит для факторизации методом SNFS: необходимозаранее найти полином f подходящей степени (оптимальная степеньполагается равной (3logNloglogN)1/3;для факторизуемых на данных момент чисел N это 4,5 или 6) с малымикоэффициентами и такое x, что f(x)0(modN), где Nчисло для факторизации. Также x должен быть таким, чтобывыполнялось ax+b0(modN) для a и b не больших N1/d.
 Одним из видов чисел, для которых такие полиномы существуют являютсячисла вида ab±1; например, когда NFSNET раскладывали число3\^479+1, они использовали полином x\^6+3 при x=3\^80, так как(3\^80)\^6+3 = 3\^480+3 и 3480+30(mod3479+1).
 У чисел, определяемых линейными рекуррентными соотношениями, таких какчисла Фибоначчи и числа Люка, тоже есть полиномы SNFS, но их немногосложнее получить. Например, F709 имеет полиномn5+10n3+10n2+10n+3, и значение x, удовлетворяющееF142xF141=0.
 Если вам известны некоторые делители большого SNFS-числа, вы можетепроизвести SNFS вычисления для оставшейся части; для примера выше отNFSNET, 3\^479+1 = (4·158071·7167757·7759574882776161031) раз197-знаковое составное число (небольших делители были исключены методомECM), и SNFS применялся для 197-значного числа. Число операций для NFSзависит от размера исходного числа, но некоторые вычисления производятсябыстрее по модулю меньшего числа.

Ограничения


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