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

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

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

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

${\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]}$

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

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

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

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

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

• Во-первых, найдите большое количество мультипликативных отношений среди факторной базы элементов Z / n Z , таких, что количество мультипликативных отношений больше, чем количество элементов в факторной базе.
• Во-вторых, перемножьте подмножества этих соотношений так, чтобы все показатели были четными, в результате чего получатся сравнения вида a ² ≡ b ² ( 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 , как и в случае рационального решета, состоит из всех простых целых чисел с точностью до некоторой другой границы.${\displaystyle N_{\max }}$

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

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

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

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

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

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

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

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

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

Ограничения алгоритма [ править ]

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

См. Также [ править ]

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

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

Дальнейшее чтение [ править ]

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