12.3.4 Метод квадратичного решета

Это один из самых широко используемых на практике методов. Его описание можно найти в работах [Pom85], [Silv]. Оценка сложности составляет , если используется гауссово исключение, и , если используется метод Копперсмита -- Винограда. Стратегии PS и EAS не используются, так как выбор значений происходит с помощью специального просеивания.

Схема алгоритма заключается в следующем. Пусть  -- факторная база (т. е. конечное множество не слишком больших простых чисел), , а . Будем просеивать значения , чтобы отыскать те, для которых разлагается в произведение простых чисел из факторной базы . Для этого:     1) для каждого находим некоторые и такие, что для ;

    2) заводим массив, пронумерованный значениями целочисленной переменной из достаточно большого интервала , и для каждого в -й элемент массива помещаем достаточно грубо вычисленное значение ;

    3) для каждого из элементов нашего массива с номерами такими, что или , вычитаем достаточно грубо вычисленное значение . После такой процедуры мы получим массив, в котором -й элемент есть грубо вычисленное значение , где .

Теперь мы отбираем те номера , для которых -е элементы массива достаточно малы, и для них разлагаем значения пробными делениями в произведение элементов факторной базы. Используя технику этапов 3 и 4 алгоритма Диксона, находим числа такие, что является квадратом натурального числа, которое мы обозначим через . С другой стороны, . Поэтому для имеем . Теперь если для некоторого , то  -- искомый нетривиальный делитель .

Преимущество такого метода заключается в том, что на стадии просеивания мы пользуемся только операцией вычитания и в итоге отбрасываем большинство "плохих" (т. е. не разлагающихся в произведение простых ) значений , в то время как в алгоритме Диксона "плохие" значения отбрасываются после деления на , что значительно дольше.