Войти
В теории чисел, общее числовое поле сито (GNFS ) является наиболее эффективным классическим алгоритмом, известным для факторизации целых чисел больше 10. эвристически, его сложность факторизации целого числа n (состоящего из ⌊log 2 n⌋ + 1 бит) имеет вид
![\ 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]](https://wikimedia.org/api/rest_v1/media/math/render/svg/fcc5450b9f039008c0a728e15b6c66f24dafbb30)
(в L-записи ), где ln - натуральный логарифм. Это обобщение решета специального числового поля : в то время как последнее может множить только числа определенной специальной формы, решето общего числового поля может множить любое число, кроме простых степеней ( которые легко разложить на множители, пустив корни).
Принцип сита числового поля (как специального, так и общего) можно понимать как усовершенствование более простого рационального сита или квадратного сита. При использовании таких алгоритмов для разложения большого числа n на множители необходимо искать гладкие числа (т.е. числа с малыми простыми множителями) порядка n. Размер этих значений экспоненциально равен размеру n (см. Ниже). Сито общего числового поля, с другой стороны, позволяет искать гладкие числа, которые являются субэкспоненциальными по размеру n. Поскольку эти числа меньше, они с большей вероятностью будут гладкими, чем числа, проверенные в предыдущих алгоритмах. Это ключ к эффективности сита числового поля. Для достижения этого ускорения решето числовых полей должно выполнять вычисления и факторизации в числовых полях. Это приводит ко многим довольно сложным аспектам алгоритма по сравнению с более простым рациональным решетом.
Размер входных данных алгоритма равен log 2 n или количеству битов в двоичном представлении n. Любой элемент порядка n для константы c является экспоненциальным в log n. Время работы сита числового поля суперполиномиально, но субэкспоненциально зависит от размера входных данных.
Предположим, что f - многочлен k-степени над Q (рациональными числами), а r - комплексный корень f. Тогда f (r) = 0, что может быть преобразовано, чтобы выразить r как линейную комбинацию степеней r, меньших k. Это уравнение можно использовать для уменьшения любых степеней r с показателем e ≥ k. Например, если f (x) = x + 1 и r - мнимая единица i, то i + 1 = 0 или i = −1. Это позволяет нам определить сложное произведение:
В общем, это ведет непосредственно к полю алгебраических чисел Q[r], которое может быть определено как набор комплексных чисел, задаваемый следующим образом:
Произведение любых двух таких значений можно вычислить, взяв произведение как многочлены, а затем уменьшив любые степени r с показателем e ≥ k, как описано выше, давая значение в той же форме. Чтобы гарантировать, что это поле действительно k-мерное и не коллапсирует до еще меньшего поля, достаточно, чтобы f был неприводимым многочленом над рациональными числами. Точно так же можно определить кольцо целых чисел OQ[r] как подмножество Q [r], которые являются корнями одночленов с целыми коэффициентами.. В некоторых случаях это кольцо целых чисел эквивалентно кольцу Z [r]. Однако есть много исключений, например, для Q [√d], когда d равно 1 по модулю 4.
Два полинома выбраны f (x) и g (x) малых степеней d и e, которые имеют целочисленные коэффициенты, которые неприводимы по рациональным числам, и которые при интерпретации mod n имеют общее целое число root m. Оптимальная стратегия выбора этих многочленов не известна; один простой метод - выбрать степень d для многочлена, рассмотреть расширение n в base m (с учетом цифр от -m до m) для числа различных m порядка n и выбрать f ( x) как многочлен с наименьшими коэффициентами и g (x) как x - m.
Рассмотрим кольца числовых полей Z[r1] и Z[r2], где r 1 и r 2 - корни многочленов f и g. Поскольку f имеет степень d с целыми коэффициентами, если a и b - целые числа, то также будет b · f (a / b), который мы называем r. Аналогично s = b · g (a / b) - целое число. Цель состоит в том, чтобы найти целые значения a и b, которые одновременно делают r и s сглаженными относительно выбранного базиса простых чисел. Если a и b малы, то r и s тоже будут маленькими, размером примерно с m, и у нас больше шансов, что они будут гладкими одновременно. Самый известный в настоящее время подход к этому поиску - это решетчатое просеивание ; Для получения приемлемых урожаев необходимо использовать большую факторную базу.
Имея достаточное количество таких пар, используя метод исключения Гаусса, можно получить произведения определенного r и соответствующего s, которые будут одновременно квадратами. Требуется немного более сильное условие - что это нормы квадратов в наших числовых полях, но это условие может быть достигнуто и этим методом. Каждый r является нормой a - r 1 b и, следовательно, произведение соответствующих коэффициентов a - r 1 b представляет собой квадрат в Z[r1] с "квадратом корень ", который может быть определен (как произведение известных факторов в Z[r1]) - обычно он будет представлен как иррациональное алгебраическое число. Аналогично, произведение множителей a - r 2 b представляет собой квадрат в Z[r2] с «квадратным корнем», который также может быть вычислен. Следует отметить, что использование исключения Гаусса не дает оптимального времени работы алгоритма. Вместо этого используются алгоритмы решения разреженных матриц, такие как Блок Ланцоша или Блок Видеманна.
Так как m является корнем из f и g по модулю n, существуют гомоморфизмы из колец Z[r1] и Z[r2] в кольцо Z/nZ(целые числа mod n ), которые отображают r 1 и r 2 в m, и эти гомоморфизмы будут отображать каждый «квадратный корень» (обычно не представляемый как рациональное число) в его целочисленного представителя. Теперь произведение множителей a - mb mod n можно получить в виде квадрата двумя способами - по одному для каждого гомоморфизма. Таким образом, можно найти два числа x и y, где x - y делится на n, и снова с вероятностью не менее половины мы получим множитель n, найдя наибольший общий делитель чисел n и x - y..
Выбор полинома может существенно повлиять на время выполнения оставшейся части алгоритма. Метод выбора полиномов, основанный на разложении n по основанию m, показанный выше, является неоптимальным во многих практических ситуациях, что приводит к разработке лучших методов.
Один из таких методов был предложен Мерфи и Брентом; они вводят двухчастную оценку для полиномов, основанную на наличии корней по модулю малых простых чисел и на среднем значении, которое полином занимает площадь просеивания.
Наилучшие результаты были достигнуты с помощью метода, который допускает g (x) = ax + b и выполняет поиск по совокупности малых простых множителей, конгруэнтных 1 по модулю 2d, и по старшим коэффициентам f, которые равны делится на 60.
Некоторые реализации ориентированы на некоторый меньший класс чисел. Они известны как методы сита специального числового поля, например, используемые в проекте Cunningham. Проект под названием NFSNET работал с 2002 по 2007 год. Он использовал добровольные распределенные вычисления в Интернете. Пол Лейланд из Соединенного Королевства и Ричард Вакербарт из Техаса
До 2007 года реализация золотого стандарта представляла собой набор программного обеспечения, разработанного и распространяемого CWI в Нидерландах, который был доступен только по относительно ограниченной лицензии. В 2007 году была разработана более быстрая реализация окончательной обработки как часть msieve, которая находится в открытом доступе. Обе реализации имеют возможность распределяться между несколькими узлами в кластере с достаточно быстрым межсоединением.
Выбор полинома обычно выполняется программным обеспечением GPL, написанным Kleinjung, или msieve, а просеивание решеток - программным обеспечением GPL, написанным Franke и Kleinjung; они распространяются в GGNFS.
