WikiDer > Специальное числовое сито

В теория чисел, филиал математика, то сито со специальным номером (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 е (х) эквив 0 { pmod {N}}}$ где N - число для факторизации. Есть дополнительное условие: Икс должен удовлетворить ${ Displaystyle топор + Ь эквив 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 эквив 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^ж, а также для многих целых чисел, двоичное представление которых имеет малый вес Хэмминга. Причина этого заключается в следующем: Сито числового поля выполняет просеивание в двух разных полях. Первое поле обычно представляет собой рациональные числа. Второй - поле более высокой степени. Эффективность алгоритма сильно зависит от норм некоторых элементов в этих полях. Когда целое число может быть представлено как многочлен с малыми коэффициентами, нормы, которые возникают, намного меньше, чем те, которые возникают, когда целое число представлено общим многочленом. Причина в том, что общий многочлен будет иметь гораздо большие коэффициенты, а нормы соответственно будут больше. Алгоритм пытается разложить эти нормы на фиксированный набор простых чисел. Когда количество форм меньше, эти числа с большей вероятностью будут иметь значение.

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

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

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

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

• Бирнс, Стивен (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