Общее числовое поле сито - General number field sieve

В теории чисел , то поле сито общего числа ( нефакторные услуги ) является наиболее эффективным классическим алгоритм известен факторинговыми целых чисел больше , чем 10 ¹⁰⁰ . Эвристический , его сложность для факторизации целого числа п (состоящие из ⌊log ₂ п ⌋ + 1 бит) имеет вида

${\ displaystyle \ exp \ left (\ left ({\ sqrt [{3}] {\ frac {64} {9}}} + o (1) \ right) (\ ln n) ^ {\ frac {1}) {3}} (\ ln \ ln n) ^ {\ frac {2} {3}} \ right) = L_ {n} \ left [{\ frac {1} {3}}, {\ sqrt [{3 }] {\ frac {64} {9}}} \ right]}$

(в L-обозначениях ), где ln - натуральный логарифм . Это обобщение решета специального числового поля : в то время как последнее может разложить на множители только числа определенной специальной формы, решето общего числового поля может разложить на множители любое число, кроме степеней простых чисел (которые тривиально разложить на множители путем извлечения корней).

Принцип сита числового поля (как специального, так и общего) можно понимать как усовершенствование более простого рационального или квадратного сита . При использовании таких алгоритмов для разложения большого числа n на множители необходимо искать гладкие числа (т. Е. Числа с малыми простыми множителями) порядка n ^1/2 . Размер этих значений экспоненциально равен размеру n (см. Ниже). Сито общего числового поля, с другой стороны, позволяет искать гладкие числа, которые являются субэкспоненциальными по размеру n . Поскольку эти числа меньше, они с большей вероятностью будут гладкими, чем числа, проверенные в предыдущих алгоритмах. Это ключ к эффективности сита числового поля. Чтобы добиться этого ускорения, решето числовых полей должно выполнять вычисления и факторизации в числовых полях . Это приводит ко многим довольно сложным аспектам алгоритма по сравнению с более простым рациональным решетом.

Размер входных данных алгоритма равен log ₂  n или количеству битов в двоичном представлении n . Любой элемент порядка n ^c для константы c является экспоненциальным в log  n . Время работы сита числового поля суперполиномиально, но субэкспоненциально зависит от размера входных данных.

Числовые поля

Предположим, что f - многочлен k -степени над Q (рациональными числами), а r - комплексный корень f . Тогда f ( r ) = 0 , что может быть преобразовано, чтобы выразить r ^k как линейную комбинацию степеней r, меньших k . Это уравнение можно использовать для уменьшения любых степеней r с показателем e ≥ k . Например, если f ( x ) =  x ²  + 1 и r - мнимая единица i , то i ²  + 1 = 0 или i ²  = −1 . Это позволяет нам определить сложный продукт:

${\ displaystyle (a + bi) (c + di) = ac + (ad + bc) i + (bd) i ^ {2} = (ac-bd) + (ad + bc) i.}$

В общем, это приводит непосредственно к полю алгебраических чисел Q [ r ] , которое можно определить как набор комплексных чисел, задаваемый следующим образом:

${\ displaystyle a_ {k-1} r ^ {k-1} + ... + a_ {1} r ^ {1} + a_ {0} r ^ {0}, {\ text {where}} a_ { 0}, ..., a_ {k-1} {\ text {in}} \ mathbf {Q}.}$

Произведение любых двух таких значений можно вычислить, взяв произведение как многочлены, а затем уменьшив любые степени r с показателем e ≥ k, как описано выше, и получим значение в той же форме. Чтобы это поле было действительно k -мерным и не коллапсировало до еще меньшего поля, достаточно, чтобы f был неприводимым многочленом над рациональными числами. Аналогично, можно определить кольцо целых чисел O _{Q [ r ]} как подмножество Q [ r ], которые являются корнями однозначных многочленов с целыми коэффициентами. В некоторых случаях это кольцо целых чисел эквивалентно кольцу Z [ r ] . Однако есть много исключений, например, для Q [ √ d ], когда d равно 1 по модулю 4.

Методика

Два многочленов F ( х ) и г ( х ) малых степени d и е выбраны, которые имеют целые коэффициенты, которые являются неприводимыми над рациональными числами , и которые, при интерпретации мод п , имеют общие целочисленные корневые м . Оптимальная стратегия выбора этих многочленов неизвестна; один простой метод - выбрать степень d для многочлена, рассмотреть расширение n по основанию m (с учетом цифр от - m до m ) для ряда различных m порядка n ^{1 / d} и выбрать f ( x ) как многочлен с наименьшими коэффициентами и g ( x ) как x  -  m .

Рассмотрим кольца числовых полей Z [ r ₁ ] и Z [ r ₂ ], где r ₁ и r ₂ - корни многочленов f и g . Поскольку f имеет степень d с целыми коэффициентами, если a и b - целые числа, то таким же будет b ^d · f ( a / b ), который мы называем r . Аналогично s = b ^e · g ( a / b ) - целое число. Цель состоит в том, чтобы найти целые значения a и b, которые одновременно делают r и s гладкими относительно выбранного базиса простых чисел. Если a и b малы, тогда r и s тоже будут маленькими, размером около m , и у нас больше шансов, что они будут гладкими одновременно. В настоящее время наиболее известным подходом к этому поиску является решетчатое просеивание ; Для получения приемлемых урожаев необходимо использовать большую факторную базу.

Имея достаточное количество таких пар, используя метод исключения Гаусса , можно получить произведения некоторых r и соответствующих s, которые будут одновременно квадратами. Требуется немного более сильное условие - что это нормы квадратов в наших числовых полях, но это условие может быть достигнуто и этим методом. Каждый r является нормой a  -  r ₁ b и, следовательно, произведение соответствующих множителей a  -  r ₁ b представляет собой квадрат в Z [ r ₁ ] с «квадратным корнем», который может быть определен (как произведение известные множители в Z [ r ₁ ]) - обычно это иррациональное алгебраическое число . Точно так же произведение множителей a  -  r ₂ b представляет собой квадрат в Z [ r ₂ ] с «квадратным корнем», который также можно вычислить. Следует отметить, что использование исключения Гаусса не дает оптимального времени выполнения алгоритма. Вместо этого используются алгоритмы решения разреженных матриц, такие как Блок Ланцоша или Блок Видеманна .

Поскольку m является корнем как f, так и g mod n , существуют гомоморфизмы из колец Z [ r ₁ ] и Z [ r ₂ ] в кольцо Z / n Z (целые числа по модулю n ), которые отображают r ₁ и r _{От 2} до m , и эти гомоморфизмы будут отображать каждый «квадратный корень» (обычно не представленный как рациональное число) в его целочисленный представитель. Теперь произведение множителей a  -  mb mod n может быть получено в виде квадрата двумя способами - по одному для каждого гомоморфизма. Таким образом, можно найти два числа х и у , с х ²  -  у ² , делящиеся на п и снова с вероятностью по крайней мере одна половина мы получаем коэффициент п , найдя наибольший общий делитель из н и х  -  у .

Улучшение полиномиального выбора

Выбор полинома может существенно повлиять на время выполнения оставшейся части алгоритма. Метод выбора полиномов, основанный на разложении n по основанию m, показанный выше, является неоптимальным во многих практических ситуациях, что приводит к разработке лучших методов.

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

Наилучшие результаты были достигнуты с помощью метода Торстена Кляйнджунга , который допускает g ( x ) = ax  +  b и выполняет поиск по a, составленному из малых простых множителей, сравнимых с 1 по модулю 2 d, и по старшим коэффициентам f, которые делятся на 60. .

Реализации

Некоторые реализации ориентированы на определенный меньший класс чисел. Они известны как специальные методы сита числового поля , такие как использованные в проекте Каннингема . Проект под названием NFSNET работал с 2002 по 2007 год. Он использовал добровольные распределенные вычисления в Интернете . В этом участвовали Пол Лейланд из Соединенного Королевства и Ричард Вакербарт из Техаса.

До 2007 года реализация золотого стандарта представляла собой набор программного обеспечения, разработанного и распространяемого CWI в Нидерландах, который был доступен только по относительно ограниченной лицензии. В 2007 году Джейсон Пападопулос разработал более быструю реализацию окончательной обработки как часть msieve, которая является общественным достоянием. Обе реализации имеют возможность распределяться между несколькими узлами в кластере с достаточно быстрым межсоединением.

Полиномиальный отбор обычно выполняется программой GPL, написанной Кляйнджунгом, или msieve, а просеивание решеток - программой GPL, написанной Франке и Кляйнджунгом; они распространяются в GGNFS.

• NFS @ Home
• GGNFS
• фактор по GNFS
• CADO-NFS
• msieve (который содержит код окончательной обработки, полиномиальный выбор, оптимизированный для меньших чисел, и реализацию линейного сита)
• кмГНФС

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

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

Заметки

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

• Мэтью Э. Бриггс: Введение в сито общего числового поля, 1998