Специальное числовое сито - Special number field sieve

В теория чисел, филиал математика, то сито со специальным номером (SNFS) - это специализированный целочисленная факторизация алгоритм. В общее числовое поле сито (GNFS) была получена из него.

Специальное сито числового поля эффективно для целых чисел вида р^е ± s, куда р и s маленькие (например Числа Мерсенна ).

Эвристически, это сложность для разложения целого числа ${\displaystyle n}$ имеет вид:^[1]

${\displaystyle \exp \left(\left(1+o(1)\right)\left({\tfrac {32}{9}}\log n\right)^{1/3}\left(\log \log n\right)^{2/3}\right)=L_{n}\left[1/3,(32/9)^{1/3}\right]}$

в О и L-обозначения.

SNFS широко используется NFSNet (волонтер распределенных вычислений усилие), NFS @ Home и другие, чтобы разложить на множители числа Каннингем проект; какое-то время записи для целочисленной факторизации данные были учтены SNFS.

Обзор метода

SNFS основана на идее, аналогичной гораздо более простой рациональное сито; в частности, читателям может быть полезно прочитать о рациональное сито во-первых, прежде чем заняться SNFS.

SNFS работает следующим образом. Позволять п быть целым числом, которое мы хотим разложить на множители. Как в рациональное сито SNFS можно разбить на два этапа:

• Сначала найдите большое количество мультипликативных отношений между факторная база элементов Z/пZ, таких, что количество мультипликативных отношений больше, чем количество элементов в факторной базе.
• Во-вторых, перемножьте подмножества этих соотношений таким образом, чтобы все показатели были четными, в результате чего получатся сравнения вида а²≡б² (мод п). Это, в свою очередь, немедленно приводит к факторизации п: п=gcd (а+б,п) × gcd (а-б,п). Если все сделано правильно, почти наверняка хотя бы одна такая факторизация будет нетривиальной.

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

Подробная информация о методе

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

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

Затем мы ищем относительно простой пары целых чисел (а,б) такой, что:

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

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

Для каждой такой пары мы можем применить гомоморфизм колец φ к факторизации а+bα, и мы можем применить канонический гомоморфизм колец из Z к Z/ пZ к факторизации а+бм. Уравнивание этих значений дает мультипликативное отношение между элементами большей факторной базы в Z/ пZ, и если мы найдем достаточно пар, мы можем перейти к объединению отношений и множителя п, как описано выше.

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

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

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

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

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

Ограничения алгоритма

Этот алгоритм, как упоминалось выше, очень эффективен для чисел вида р^е±s, за р и s относительно маленький. Он также эффективен для любых целых чисел, которые можно представить в виде многочлена с малыми коэффициентами. Сюда входят целые числа более общего вида ар^е±bs^ж, а также для многих целых чисел, двоичное представление которых имеет малый вес Хэмминга. Причина этого заключается в следующем: Сито числового поля выполняет просеивание в двух разных полях. Первое поле обычно представляет собой рациональные числа. Второй - поле более высокой степени. Эффективность алгоритма сильно зависит от норм некоторых элементов в этих полях. Когда целое число может быть представлено как многочлен с малыми коэффициентами, нормы, которые возникают, намного меньше, чем те, которые возникают, когда целое число представлено общим многочленом. Причина в том, что общий многочлен будет иметь гораздо большие коэффициенты, а нормы соответственно будут больше. Алгоритм пытается разложить эти нормы на фиксированный набор простых чисел. Когда количество форм меньше, эти числа с большей вероятностью будут иметь значение.

Смотрите также

• Общее числовое поле сито

Рекомендации

1. Померанс, Карл (Декабрь 1996 г.), «Сказка о двух решетах» (PDF), Уведомления AMS, 43 (12), стр. 1473–1485.
2. Франке, Йенс. «Замечания по установке для ggnfs-lasieve4». Массачусетский технологический институт Массачусетский Институт Технологий.

дальнейшее чтение

• Бирнс, Стивен (18 мая 2005 г.), "Сито числового поля" (PDF), Математика 129
• Ленстра, А.К.; Ленстра, Х. В., мл.; Манассе, М. С. и Поллард, Дж. М. (1993), «Факторизация девятого числа Ферма», Математика вычислений, 61 (203): 319–349, Bibcode:1993MaCom..61..319L, Дои:10.1090 / S0025-5718-1993-1182953-4
• Ленстра, А. К .; Ленстра, Х. В., младший, ред. (1993), Развитие сита числового поля, Конспект лекций по математике, 1554, Нью-Йорк: Springer-Verlag, ISBN  978-3-540-57013-4
• Сильверман, Роберт Д. (2007), "Оптимальная параметризация SNFS", Журнал математической криптологии, 1 (2): 105–124, CiteSeerX  10.1.1.12.2975, Дои:10.1515 / JMC.2007.007