Введение
В теории чисел, являющейся разделом математики, специальное решето числового поля (SNFS) — это алгоритм целочисленной факторизации специального назначения. Общее решето числового поля (GNFS) было выведено из него. Специальное решето числового поля эффективно для целых чисел вида re ± s, где r и s малы (например, числа Мерсенна). Эвристически, его сложность для факторизации целого числа выражается в виде: в нотации O и L. SNFS широко использовалось NFSNet (добровольческим распределённым вычислительным проектом), NFS@Home и другими для факторизации чисел в рамках проекта Каннингема; некоторое время рекорды по факторизации целых чисел принадлежали числам, разложенным с помощью SNFS.
in O and L notations. The SNFS has been used extensively by NFSNet (a volunteer distributed computing effort), NFS@Home and others to factorise numbers of the Cunningham project; for some time the records for integer factorization have been numbers factored by SNFS.
Обзор метода
SNFS основана на идее, аналогичной гораздо более простому рациональному ситу; в частности, читателям может быть полезно ознакомиться с рациональным ситом, прежде чем приступать к SNFS. SNFS работает следующим образом. Пусть n – целое число, которое мы хотим разложить на множители. Как и в рациональном сите, SNFS можно разделить на два этапа: во-первых, найти большое количество мультипликативных соотношений между элементами факторбазы Z/nZ, так чтобы количество этих соотношений превышало количество элементов в факторбазе. Во-вторых, перемножить подмножества этих соотношений таким образом, чтобы все степени были четными, в результате чего получатся сравнения вида a² ≡ b² (mod n). Эти сравнения, в свою очередь, непосредственно приводят к разложению n на множители: n = НОД(a+b, n) × НОД(a-b, n). Если все сделано правильно, то почти наверняка хотя бы одно такое разложение будет нетривиальным. Второй этап идентичен случаю рационального сита и представляет собой простую задачу линейной алгебры. Однако первый этап выполняется другим, более эффективным способом, чем в рациональном сите, с использованием полей чисел.
First, find a large number of multiplicative relations among a factor base of elements of Z/nZ, such that the number of multiplicative relations is larger than the number of elements in the factor base. Second, multiply together subsets of these relations in such a way that all the exponents are even, resulting in congruences of the form a2≡b2 (mod n). These in turn immediately lead to factorizations of n: n=gcd(a+b,n)×gcd(a b,n). If done right, it is almost certain that at least one such factorization will be nontrivial. The second step is identical to the case of the rational sieve, and is a straightforward linear algebra problem. The first step, however, is done in a different, more efficient way than the rational sieve, by utilizing number fields.
Выбор параметров
Не каждое число является подходящим выбором для SNFS: необходимо заранее знать многочлен f соответствующей степени (оптимальная степень, как предполагается, равна 4, 5 или 6 для размеров N, которые в настоящее время возможно разложить на множители) с небольшими коэффициентами, и значение x такое, что , где N – число, которое требуется разложить на множители. Существует дополнительное условие: x должно удовлетворять для a и b, не превышающих . Одним из наборов чисел, для которых существуют такие многочлены, являются числа из таблиц Каннингема; например, когда NFSNET разложил 1=3^{479}+1, они использовали многочлен 1=x^6+3 с 1=x=3^{80}, поскольку 1=(3^{80})^6+3 = 3^{480}+3. Числа, определяемые линейными рекурренциями, такие как числа Фибоначчи и Люка, также имеют SNFS-полиномы, но их немного сложнее построить. Например, имеет многочлен , а значение x удовлетворяет . Если уже известны некоторые факторы большого числа, совместимые с SNFS, то можно выполнить вычисление SNFS по модулю оставшейся части; в примере NFSNET выше, 1=3^{479}+1 = (2^2 × 158071 × 7167757 × 7759574882776161031) умноженное на 197-значное составное число (малые факторы были найдены с помощью ECM), и SNFS выполнялся по модулю этого 197-значного числа. Количество отношений, необходимых SNFS, по-прежнему зависит от размера большого числа, но отдельные вычисления быстрее по модулю меньшего числа.
One set of numbers for which such polynomials exist are the numbers from the Cunningham tables; for example, when NFSNET factored 1=3^{479}+1, they used the polynomial 1=x^6+3 with 1=x=3^{80} , since 1=(3^{80})^6+3 = 3^{480}+3, and
Numbers defined by linear recurrences, such as the Fibonacci and Lucas numbers, also have SNFS polynomials, but these are a little more difficult to construct. For example, has polynomial , and the value of x satisfies
If one already knows some factors of a large number compatible with SNFS, then one could do the SNFS calculation modulo the remaining part; for the NFSNET example above, 1=3^{479}+1 = (2^2 \times 158071 \times 7167757 \times 7759574882776161031) times a 197 digit composite number (the small factors were found by ECM), and the SNFS was performed modulo the 197 digit number. The number of relations required by SNFS still depends on the size of the large number, but the individual calculations are quicker modulo the smaller number.
Ограничения алгоритма
Этот алгоритм, как упоминалось выше, очень эффективен для чисел вида re±s, где r и s относительно невелики. Он также эффективен для любых целых чисел, которые можно представить в виде многочлена с небольшими коэффициентами. Это относится к целым числам более общей формы are±bsf, а также ко многим целым числам, двоичное представление которых имеет малый вес Хамминга. Причина этого в следующем: "Решето числового поля" выполняет просеивание в двух различных полях. Первое поле обычно – поле рациональных чисел. Второе – поле более высокой степени. Эффективность алгоритма сильно зависит от норм определенных элементов в этих полях. Когда целое число можно представить в виде многочлена с небольшими коэффициентами, возникающие нормы значительно меньше, чем те, которые возникают при представлении целого числа общим многочленом. Это связано с тем, что общий многочлен будет иметь гораздо большие коэффициенты, а нормы будут соответственно больше. Алгоритм пытается разложить эти нормы на множители над фиксированным набором простых чисел. Когда нормы меньше, эти числа с большей вероятностью будут разложены на множители.
norms are smaller, these numbers are more likely to factor.