Специальное номерное сито поля - Special number field sieve

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

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

Эвристический , его сложность для факторизации целого числа имеет вида:

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

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

Обзор метода

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ссылки

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