Метод квадратичного решета (Quadratic sieve algorithm, сокр. QS) — метод факторизации больших чисел, разработанный Померанцем в 1981 году. Долгое время превосходил другие методы факторизации целых чисел общего вида, не имеющих простых делителей, порядок которых значительно меньше (для чисел , имеющих простые делители, много меньшие более быстрым является метод факторизации на эллиптических кривых). Метод квадратичного решета представляет собой разновидность метода факторных баз (обобщение метода факторизации Ферма). Этот метод считается вторым по быстроте (после общего метода решета числового поля). И до сих пор является самым быстрым для целых чисел до 100 десятичных цифр и устроен значительно проще чем общий метод решета числового поля. Это универсальный алгоритм факторизации, так как время его выполнения исключительно зависит от размера факторизуемого числа, а не от его особой структуры и свойств.

Основная идея метода

В качестве факторной базы берется множество простых чисел, состоящее из и всех таких нечетных простых чисел , не превосходящих заданной границы (которая выбирается из соображений оптимальности), что  — квадратичный вычет по модулю .

Множество целых чисел, в котором ищутся -числа (-число — целое число, делящееся только на простые числа из ) выглядит следующим образом:

Далее, вместо того, чтобы брать одно за другим , и делить его на простые числа из , берутся одно за другим каждое и проверяется делимость на (и его степени) одновременно для всех . Для построения списка всех простых , не превосходящих , можно использовать решето Эратосфена.

Алгоритм

1. Выбираются границы и порядка величины (далее обозначается как ), такие что .

2. Для , ,…, по порядку в столбец выписываются целые числа .

3. Для каждого нечетного простого числа проверяется условие . Если оно не выполняется, удаляется из факторной базы.

4. Предполагая, что  — такое нечетное простое число, что  — квадратичный вычет по модулю , решается уравнение для 1,2,… . Значения берутся в порядке возрастания пока не окажется, что уравнение не имеет решений , сравнимых по модулю с каким-либо из чисел в области .

Пусть  — наибольшее из таких чисел, для которых в указанной области найдется число со свойством .

Пусть и решения и .

5. При том же значении просматривается список значений , полученный в п.2. В столбце, соответствующем , ставится 1 против всех значений , для которых отличается от на некоторое кратное . После этого 1 заменяется на 2 для всех таких значений , что отличается от на кратное и т. д. до . Затем то же самое проделывается с вместо . Наибольшее возможное число в столбце — .

6. При добавлении очередной единицы к числу в столбце в п.5, соответствующее число делится на и полученный результат сохраняется.

7. В столбце под при просто ставится 1 против с нечетным и соответствующее делится на 2. При решается уравнение и решение продолжается в том же ключе, как при нечетном .

8. Когда все указанные действия будут проведены для всех простых чисел, не превосходящих , следует отбросить все числа , кроме обратившихся в 1 после деления на все степени , не превосходящих . В итоге получится таблица, в которой в столбце будут содержаться все такие значения из интервала , что есть -число, а остальные столбцы будут соответствовать тем значениям , для которых  — квадратичный вычет.

9. Далее используется обобщенный метод факторизации Ферма (метод факторных баз).

Литература

• Koblitz N.A. Course in number theory and cryptography. — Springer-Verlag, 1987. — P. 180-182.
• Gerver J.L. Factoring large numbers with a quadratic sieve. — Math. Comp., 1983. — Vol. 41. — P. 287-294.