Сито с полем специального номера

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

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

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

$\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 и другими для факторизации чисел проекта Каннингема ; в течение некоторого времени записями для факторизации целых чисел были числа, факторизованные SNFS.

Обзор метода

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

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

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

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

Подробности метода

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

• Сито общего числового поля

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

• Бирнс, Стивен (18 мая 2005 г.), «Сито числового поля» (PDF) , Math 129
• Ленстра, АК ; Ленстра, Х.В. младший ; Манасс, М.С. и Поллард, Дж.М. (1993), «Факторизация девятого числа Ферма», Mathematics of Computation , 61 (203): 319–349, Bibcode : 1993MaCom..61..319L , doi : 10.1090/S0025- 5718-1993-1182953-4 , HDL : 1887/2150
• Ленстра, АК; Ленстра, 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 , S2CID   16236028