12.4 Метод решета числового поля

В работе [LLMP] описан метод факторизации чисел вида , где и невелики, с эвристической оценкой сложности , где . Этот метод называется методом решета числового поля. С его помощью было разложено на множители число . Суть метода заключается в том, что мы переходим в некоторое алгебраическое расширение поля рациональных чисел и перебором , , ищем элементы , которые разлагаются на множители в некоторой факторной базе. Перебор и делается с помощью специального просеивания, наподобие метода квадратичного решета. Затем с помощью одного из методов исключения находят соотношение . Тогда если для некоторого , то  -- искомый нетривиальный делитель .

Имеется также препринт [BuhLP], в котором описан алгоритм факторизации произвольного со сложностью арифметических операций.

Имеются и другие работы в этом направлении (см. [Adl91]).