Введение

Алгоритм факторизации
В теории чисел общее решето числового поля (GNFS) является наиболее эффективным известным классическим алгоритмом для факторизации целых чисел, больших 10^(100). Эвристически, его сложность для факторизации целого числа n (состоящего из битов) имеет вид в обозначениях O и L. Это обобщение специального решета числового поля: в то время как последнее может факторизовать только числа определенной специальной формы, общее решето числового поля может факторизовать любое число, кроме степеней простых чисел (которые тривиально факторизуются извлечением корня). Принцип решета числового поля (как специального, так и общего) можно понимать как улучшение более простых рационального или квадратичного решета. При использовании таких алгоритмов для факторизации большого числа n необходимо искать гладкие числа (т.е. числа с небольшими простыми множителями) порядка n^(1/2). Размер этих значений экспоненциален относительно размера n (см. ниже). Общее решето числового поля, напротив, позволяет искать гладкие числа, которые являются субэкспоненциальными относительно размера n. Поскольку эти числа меньше, они с большей вероятностью будут гладкими, чем числа, проверяемые в предыдущих алгоритмах. Это является ключом к эффективности решета числового поля. Для достижения этого ускорения решето числового поля должно выполнять вычисления и факторизации в числовых полях. Это приводит ко многим довольно сложным аспектам алгоритма по сравнению с более простым рациональным решетом. Размер входных данных для алгоритма равен log2 n или количеству битов в двоичном представлении n. Любой элемент порядка n^(c) для константы c является экспоненциальным относительно log n. Время работы решета числового поля является суперполиномиальным, но субэкспоненциальным относительно размера входных данных.

Метод

Выбираются два многочлена f(x) и g(x) малых степеней d и e, которые имеют целые коэффициенты, являются неприводимыми над рациональными числами и, при интерпретации по модулю n, имеют общий целочисленный корень m. Оптимальная стратегия выбора этих многочленов неизвестна; один из простых методов — выбрать степень d для многочлена, рассмотреть представление n в системе счисления по основанию m (допуская цифры между −m и m) для ряда различных m порядка n<sup>1/d</sup>, и выбрать f(x) как многочлен с наименьшими коэффициентами, а g(x) как x − m.

Рассмотрим кольца целых чисел Z[r<sub>1</sub>] и Z[r<sub>2</sub>], где r<sub>1</sub> и r<sub>2</sub> — корни многочленов f и g соответственно. Поскольку f имеет степень d с целыми коэффициентами, если a и b — целые числа, то bd·f(a/b) также будет целым числом, обозначим его r. Аналогично, s = be·g(a/b) — целое число. Цель состоит в том, чтобы найти целые значения a и b, которые одновременно делают r и s гладкими относительно выбранного базиса простых чисел. Если a и b малы, то r и s тоже будут малы, примерно того же порядка, что и m, и у нас будет больше шансов, что они будут гладкими одновременно. Наиболее эффективный известный на данный момент метод поиска — решетчатое просеивание; для получения приемлемой производительности необходимо использовать большой базис простых множителей. Имея достаточно таких пар, с помощью метода Гаусса можно получить произведения определенных r и соответствующих s, которые будут одновременно являться полными квадратами. Требуется немного более сильное условие — чтобы они были нормами квадратов в наших числовых полях, но этого условия также можно достичь этим методом. Каждый r является нормой выражения a − r<sub>1</sub>b, и, следовательно, произведение соответствующих множителей a − r<sub>1</sub>b является квадратом в Z[r<sub>1</sub>], с "квадратным корнем", который можно определить (как произведение известных множителей в Z[r<sub>1</sub>]) — обычно он будет представлен в виде иррационального алгебраического числа. Аналогично, произведение множителей a − r<sub>2</sub>b является квадратом в Z[r<sub>2</sub>], с "квадратным корнем", который также можно вычислить. Следует отметить, что использование метода Гаусса не обеспечивает оптимальное время работы алгоритма. Вместо этого используются алгоритмы решения разреженных матриц, такие как Block Lanczos или Block Wiedemann. Поскольку m является корнем f и g по модулю n, существуют гомоморфизмы из колец Z[r<sub>1</sub>] и Z[r<sub>2</sub>] в кольцо Z/nZ (целые числа по модулю n), которые отображают r<sub>1</sub> и r<sub>2</sub> в m, и эти гомоморфизмы отображают каждый "квадратный корень" (обычно не представленный в виде рационального числа) в его целочисленное представление. Теперь произведение множителей a − mb по модулю n можно получить в виде квадрата двумя способами — по одному для каждого гомоморфизма. Таким образом, можно найти два числа x и y, такие что x<sup>2</sup> − y<sup>2</sup> делится на n, и снова с вероятностью не менее половины мы получим фактор n, найдя наибольший общий делитель n и x − y.

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

Выбор полинома может существенно повлиять на время завершения остальной части алгоритма. Метод выбора полиномов, основанный на представлении числа n в системе счисления по основанию m, описанный выше, часто оказывается неоптимальным на практике, что привело к разработке более эффективных методов. Один из таких методов был предложен Мерфи и Брентом; они ввели двухкомпонентную оценку для полиномов, основанную на наличии корней по модулю малых простых чисел и на среднем значении, которое полином принимает в области просеивания. Наилучшие результаты были достигнуты методом Торстена Клейнюнга, который позволяет осуществлять поиск по множеству, состоящему из малых простых множителей, сравнимых с 1 по модулю 2d, и по старшим коэффициентам f, делящимся на 60.